Abstract Background Human immunodeficiency virus (HIV) type 1 and 2, the causative agents of acquired immunodeficiency syndrome (AIDS), emerged from African non-human primates (NHPs) through zoonotic transmission of simian immunodeficiency viruses (SIV). Among African NHPs, the Cercopithecus genus contains the largest number of species known to harbor SIV. However, our understanding of the diversity and evolution of SIVs infecting this genus is limited by incomplete taxonomic and geographic sampling, particularly in East Africa. In this study, we screened blood specimens from red-tailed guenons ( Cercopithecus ascanius schmidti ) from Kibale National Park, Uganda, for the presence of novel SIVs using unbiased deep-sequencing. Findings We describe and characterize the first full-length SIV genomes from wild red-tailed guenons in Kibale National Park, Uganda. This new virus, tentatively named SIVrtg_Kib, was detected in five out of twelve animals and is highly divergent from other Cercopithecus SIVs as well as from previously identified SIVs infecting red-tailed guenons, thus forming a new SIV lineage. Conclusions Our results show that the genetic diversity of SIVs infecting red-tailed guenons is greater than previously appreciated. This diversity could be the result of cross-species transmission between different guenon species or limited gene flow due to geographic separation among guenon populations.