Recent advances in noninvasive detection methods for mycobacterial infection in primates create new opportunities for exploring the epidemiology of tuberculosis in free-living species. Chimpanzees (Pan troglodytes schweinfurthii) and baboons (Papio anubis) in Gombe National Park, Tanzania, were screened for infection with pathogens of the Mycobacterium tuberculosis Complex using Fecal IS6110 PCR; none was positive. This study demonstrates the feasibility of large-scale mycobacterial screening in wild primates.