Prokaryotic systematics provides the fundamental framework for microbiological research but remains a discipline that relies on a labour- and time-intensive polyphasic taxonomic approach, including DNA-DNA hybridization, variation in 16S rRNA gene sequence and phenotypic characteristics. These techniques suffer from poor resolution in distinguishing between closely related species and often result in misclassification and misidentification of strains. Moreover, guidelines are unclear for the delineation of bacterial genera. Here, we have applied an innovative phylogenetic and taxogenomic approach to a heterogeneous actinobacterial taxon, Rhodococcus, to identify boundaries for intrageneric and supraspecific classification. Seven species-groups were identified within the genus Rhodococcus that are as distantly related to one another as they are to representatives of other mycolic acid containing actinobacteria and can thus be equated with the rank of genus. It was also evident that strains assigned to rhodococcal species-groups are underspeciated with many misclassified using conventional taxonomic criteria. The phylogenetic and taxogenomic methods used in this study provide data of theoretical value for the circumscription of generic and species boundaries and are also of practical significance as they provide a robust basis for the classification and identification of rhodococci of agricultural, industrial and medical/veterinary significance.