A previously unidentified, slowly growing scotochromogenic Mycobacterium was isolated from a Korean patient with symptomatic pulmonary infection. Phenotypically, this strain was generally similar to Mycobacterium terrae complex strains, however it uniquely produced orange pigmentation. Unique mycolic acid profiles and phylogenetic analyses based on three alternative chronometer molecules, 16S rRNA gene, hsp65 and rpoB, confirmed the taxonomic status of this strain as a novel species. These results support that this strain represents a novel Mycobacterium species. The name Mycobacterium paraterrae sp. nov. is proposed. The type strain is 05-2522 (= DSM 45127 = KCTC 19556).