The isolation of nontuberculous mycobacteria (NTM) raises the question of their clinical significance, especially in an African setting. We found a high percentage of NTM isolated from various specimens, including ones that are normally sterile, among 213 patients in Zambia. Because tuberculosis can affect all parts of the body, we decided to include patients who had signs and symptoms in any part of the body for more than 2 weeks. Most patients had tractus respiratorius (80%) and tractus digestivus (10%) symptoms. During three consecutive days, sputum was collected and two separate sputum specimens were cultured for mycobacteria. Depending on the clinical picture, pleural effusion, ascites, abscess material, or enlarged lymph nodes were also cultured for mycobacteria. A specimen from one sterile body site was collected from 25 patients (60% human immunodeficiency virus [HIV] positive). NTM were isolated from 8 of these 25 specimens. Mycobacterium lentiflavum was isolated from four patients, and Mycobacterium goodii was isolated from one patient. In order to exclude the possibility of laboratory cross-contamination, a novel amplified fragment length polymorphism DNA typing method for M. lentiflavum was developed. Genetic variation was detected, rendering the likelihood of laboratory contamination unlikely. Clinically relevant infection due to NTM occurs in both HIV-positive and HIV-negative patients in Zambia, and their clinical impact seems to be underestimated. This is the first report of M. lentiflavum and M. goodii infections in Africa.