It can be difficult to establish the clinical significance of the isolation of non-tuberculous mycobacteria (NTM) from the sputum of HIV-infected patients. In this observational study, we have investigated factors associated with having NTM infection. During the period of the study, 10 patients had NTM infection and 14 had NTM colonization. Factors associated with having NTM infections were: CD4 lymphocyte count <50 cells/mL (odds ratio [OR] 10; 95% confidence interval [CI] 1.4-69.3), haemoglobin <11 g/dL (OR 7.2; 95% CI 1.08-47.9), weight loss (OR 9; 95% CI 1.3-63.9), duration of symptoms for more than a month (OR 54; 95% CI 4.2-692.5), the presence of acid fast bacilli (AFB) in sputum (OR 30.3; 95% CI 2.6-348.9) and repeated positive NTM cultures in other sputum samples (OR 4.3; 95% CI 1.6-11.7). In conclusion, we must suspect NTM infection in patients with long-standing symptoms, anaemia, low CD4 lymphocyte count, several positive sputum cultures and when AFB are seen.