The Bovini species comprise both domestic and wild cattle species. Published phylogenies of this tribe based on mitochondrial DNA contain anomalies, while nuclear sequences show only low variation. We have used amplified fragment length polymorphism (AFLP) fingerprinting in order to detect variation in loci distributed over the nuclear genome. Computer-assisted scoring of electrophoretic fingerprinting patterns yielded 361 markers, which provided sufficient redundancy to suppress stochastic effects of intraspecies polymorphisms and length homoplasies (comigration of non-homologous fragments). Tree reconstructions reveal three clusters: African buffalo with water buffalo, ox with zebu, and bison with wisent. Similarity values suggest a clustering of gaur and banteng, but bifurcating clustering algorithms did not assign consistent positions to these species and yak. We propose that because of shared polymorphisms and reticulations, tree topologies are only partially adequate to represent the phylogeny of the Bovini. Principal-coordinate analysis positions zebu between a gaur/banteng cluster and taurine cattle. This correlates with the region of origin of these species and suggests that genomic distances between the cattle species have been influenced by genetic exchange between neighbouring ancestral populations.