Background: Propionibacteria are part of the human microbiota. Many studies have addressed the predominant colonizer of sebaceous follicles of the skin, Propionibacterium acnes, and investigated its association with the skin disorder acne vulgaris, and lately with prostate cancer. Much less is known about two other propionibacterial species frequently found on human tissue sites, Propionibacterium granulosum and Propionibacterium avidum. Here we analyzed two and three genomes of P. granulosum and P. avidum, respectively, and compared them to two genomes of P. acnes; we further highlight differences among the three cutaneous species with proteomic and microscopy approaches. Results: Electron and atomic force microscopy revealed an exopolysaccharide (EPS)-like structure surrounding P. avidum cells, that is absent in P. acnes and P. granulosum. In contrast, P. granulosum possesses pili-like appendices, which was confirmed by surface proteome analysis. The corresponding genes were identified; they are clustered with genes encoding sortases. Both, P. granulosum and P. avidum lack surface or secreted proteins for predicted host-interacting factors of P. acnes, including several CAMP factors, sialidases, dermatan-sulphate adhesins, hyaluronidase and a SH3 domain-containing lipoprotein; accordingly, only P. acnes exhibits neuraminidase and hyaluronidase activities. These functions are encoded on previously unrecognized island-like regions in the genome of P. acnes. Conclusions: Despite their omnipresence on human skin little is known about the role of cutaneous propionibacteria. All three species are associated with a variety of diseases, including postoperative and device-related abscesses and infections. We showed that the three organisms have evolved distinct features to interact with their human host. Whereas P. avidum and P. granulosum produce an EPS-like surface structure and pili-like appendices, respectively, P. acnes possesses a number of unique surface-exposed proteins with host-interacting properties. The different surface properties of the three cutaneous propionibacteria are likely to determine their colonizing ability and pathogenic potential on the skin and at non-skin sites.