Polycyclic aromatic hydrocarbons (PAHs) are widespread environmental contaminants. In this study, both pristine and contaminated soils were sampled as a source of PAH-degrading organisms. Nine strains isolated from these soils were identified as rapidly growing members of the genus Mycobacterium through basic phenotypic characteristics and through sequence similarity of three genes. Because the sequence similarity of the 16S rRNA gene is relatively high among members of this genus, additional conserved genes encoding the beta subunit of RNA polymerase (rpoB) and a heat-shock protein (hsp65) were sequenced. Several analyses were completed to differentiate the strains from one another and to determine their species-level taxonomy, including fatty acid methyl ester analysis, biochemical tests and substrate-utilization profiling. A phylogenetic tree incorporating sequences for all three genes was constructed with the isolates and their close described relatives. Results for biochemical tests, substrate-utilization tests and DNA sequencing were compared with those of the phylogenetically similar organisms to establish the isolated strains as representatives of novel species with characteristics unlike those of previously described species of Mycobacterium. Finally, DNA-DNA hybridization was performed between strains and their close relatives to confirm their position within novel species. Our results demonstrated that the isolates represent five novel species, which were named Mycobacterium crocinum sp. nov. (type strain czh-42(T) =ATCC BAA-1373(T) =CIP 109262(T); reference strains czh-1A =ATCC BAA-1370 =CIP 109266 and czh-3 =ATCC BAA-1371=CIP 109267), Mycobacterium pallens sp. nov. (type strain czh-8(T) =ATCC BAA-1372(T) =CIP 109268(T)), Mycobacterium rutilum sp. nov. (type strain czh-117(T) =ATCC BAA-1375(T) =CIP 109271(T); reference strains czh-107 =ATCC BAA-1374 =CIP 109270 and czh-132 =ATCC BAA-1376 =CIP 109272), Mycobacterium rufum sp. nov. (type strain JS14(T) =ATCC BAA-1377(T) =CIP 109273(T)) and Mycobacterium aromaticivorans sp. nov. (type strain JS19b1(T) =ATCC BAA-1378(T) =CIP 109274(T)).