The genus Corynebacterium encompasses many species of biotechnological, medical or veterinary significance. An important characteristic of this genus is the presence of mycolic acids in their cell envelopes, which form the basis of a protective outer membrane (mycomembrane). Mycolic acids in the cell envelope of Mycobacterium tuberculosis have been associated with virulence. In this study, we have analysed the genomes of 140 corynebacterial strains, including representatives of 126 different species. More than 50% of these strains were isolated from clinical material from humans or animals, highlighting the true scale of pathogenic potential within the genus. Phylogenomically, these species are very diverse and have been organised into 19 groups and 30 singleton strains. We find that a substantial number of corynebacteria lack FAS-I, i.e., have no capability for de novo fatty acid biosynthesis and must obtain fatty acids from their habitat; this appears to explain the well-known lipophilic phenotype of some species. In most species, key genes associated with the condensation and maturation of mycolic acids are present, consistent with the reports of mycolic acids in their species descriptions. Conversely, species reported to lack mycolic acids lacked these key genes. Interestingly, Corynebacterium ciconiae, which is reported to lack mycolic acids, appears to possess all genes required for mycolic acid biosynthesis. We suggest that although a mycolic acid-based mycomembrane is widely considered to be the target for interventions by the immune system and chemotherapeutics, the structure is not essential in corynebacteria and is not a prerequisite for pathogenicity or colonisation of animal hosts.