Three children with human immunodeficiency virus infection and invasive infection with Mycobacterium genavense are reported. Fever spikes, abdominal cramps and distension, diarrhea or ileus, and anemia were the predominant symptoms in the severely immunodeficient patients (CD4 lymphocytes < 0.04 x 10(9)/l). Numerous acid-fast bacilli were readily detectable by microscopy in stool samples and in lymph node biopsies, but cultures for mycobacteria remained negative. Mycobacterium genavense should be sought when invasive non-tuberculous mycobacteriosis is suspected and mycobacterial cultures from blood or other sites show limited growth. Multiple-drug regimens including amikacin, ethambutol, rifampin, and clarithromycin may be of benefit in controlling the infection, as observed in two patients.