Data on nontuberculous mycobacterial (NTM) disease in sub-Saharan Africa are limited. During 2006-2008, we identified 3 HIV-infected patients in northern Tanzania who had invasive NTM; 2 were infected with "Mycobacterium sherrisii" and 1 with M. avium complex sequevar MAC-D. Invasive NTM disease is present in HIV-infected patients in sub-Saharan Africa.