It has been known for decades that wild baboons are naturally infected with Treponema pallidum, the bacterium that causes the diseases syphilis (subsp. pallidum), yaws (subsp. pertenue), and bejel (subsp. endemicum) in humans. Recently, a form of T. pallidum infection associated with severe genital lesions has been described in wild baboons at Lake Manyara National Park in Tanzania. In this study, we investigated ten additional sites in Tanzania and Kenya using a combination of macroscopic observation and serology, in order to determine whether the infection was present in each area. In addition, we obtained genetic sequence data from six polymorphic regions using T. pallidum strains collected from baboons at two different Tanzanian sites. We report that lesions consistent with T. pallidum infection were present at four of the five Tanzanian sites examined, and serology was used to confirm treponemal infection at three of these. By contrast, no signs of treponemal infection were observed at the six Kenyan sites, and serology indicated T. pallidum was present at only one of them. A survey of sexually mature baboons at Lake Manyara National Park in 2006 carried out as part of this study indicated that roughly ten percent displayed T. pallidum-associated lesions severe enough to cause major structural damage to the genitalia. Finally, we found that T. pallidum strains from Lake Manyara National Park and Serengeti National Park were genetically distinct, and a phylogeny suggested that baboon strains may have diverged prior to the clade containing human strains. We conclude that T. pallidum infection associated with genital lesions appears to be common in the wild baboons of the regions studied in Tanzania. Further study is needed to elucidate the infection’s transmission mode, its associated morbidity and mortality, and the relationship between baboon and human strains.