Mycobacterium tuberculosis is a common cause of bloodstream infections among HIV-infected adults in sub-Saharan Africa, and is associated with high morbidity and mortality. We found no cases of mycobacteremia among 93 ill, HIV-infected children in northern Tanzania, despite optimization of laboratory methods and selection of patients thought to be at highest risk for disseminated infection.