The headwaters of five large African river basins flow through the Bié Plateau in Angola and still remain faunistically largely unexplored. We investigated fish fauna from the Cuanza and Okavango-Zambezi river systems from central Angola. We reconstructed molecular phylogenies of the most common cichlid species from the region, Tilapia sparrmanii and Serranochromis macrocephalus, using both mitochondrial and nuclear markers. We found evidence for ichthyofaunal contact and gene flow between the Cuanza and Okavango-Zambezi watersheds in the Bié Plateau in central Angola. Waterfalls and rapids also appeared to restrict genetic exchange among populations within the Cuanza basin. Further, we found that the Angolan Serranochromis cichlid fishes represent a monophyletic lineage with respect to other haplochromines, including the serranochromines from the Congo and Zambezi rivers. This study represents an important initial step in a biodiversity survey of this extremely poorly explored region, as well as giving further understanding to species distributions and gene flow both between and within river basins.