Background: Gorongosa National Park in Mozambique hosts a large population of baboons, numbering over 200 troops. Gorongosa baboons have been tentatively identified as part of Papio ursinus on the basis of previous limited morphological analysis and a handful of mitochondrial DNA sequences. However, a recent morphological and morphometric analysis of Gorongosa baboons pinpointed the occurrence of several traits intermediate between P. ursinus and P. cynocephalus, leaving open the possibility of past and/or ongoing gene flow in the baboon population of Gorongosa National Park. In order to investigate the evolutionary history of baboons in Gorongosa, we generated high and low coverage whole genome sequence data of Gorongosa baboons and compared it to available Papio genomes. Results: We confirmed that P. ursinus is the species closest to Gorongosa baboons. However, the Gorongosa baboon genomes share more derived alleles with P. cynocephalus than P. ursinus does, but no recent gene flow between P. ursinus and P. cynocephalus was detected when available Papio genomes were analyzed. Our results, based on the analysis of autosomal, mitochondrial and Y chromosome data, suggest complex, possibly male-biased, gene flow between Gorongosa baboons and P. cynocephalus, hinting to direct or indirect contributions from baboons belonging to the “northern” Papio clade, and signal the presence of population structure within P. ursinus. Conclusions: The analysis of genome data generated from baboon samples collected in central Mozambique highlighted a complex set of evolutionary relationships with other baboons. Our results provided new insights in the population dynamics that have shaped baboon diversity.