We identified 2 novel species, Mycobacterium novusgordonae and M. shingordonae, from sputum specimens of pulmonary disease patients in Japan. Genetic and biochemical analyses revealed a close relationship with M. paragordonae. One M. shingordonae case-patient experienced severe progressive infection, highlighting the variation in pathogenicity of the M. gordonae clade species.