Fourteen mycobacterial strains isolated from pulmonary samples of independent patients in the state of Pará (Brazil), and three strains isolated in Italy, were characterized using a polyphasic approach. Thorough genetic investigation, including whole-genome sequencing, demonstrated that the strains belong to the M. simiae complex, being most closely related to Mycobacterium interjectum. For 14 of the strains, evidence emerged supporting their inclusion in a previously unreported species of the genus Mycobacterium, for which the name Mycobacterium paraense sp. nov. is proposed (type strain, IEC26(T) = DSM 46749(T) = CCUG 66121(T)). The novel species is characterized by slow growth, unpigmented or pale yellow scotochromogenic colonies, and a HPLC mycolic acid profile different from other known mycobacteria. In different genetic regions, high sequence microheterogeneity was detected.