To clarify the origin and evolution of the primate lentiviruses (PLVs), which include human immunodeficiency virus types 1 and 2 as well as their simian relatives, simian immunodeficiency viruses (SIVs), isolated from several host species, we investigated the phylogenetic relationships among the six supposedly nonrecombinant PLV lineages for which the full genome sequences are available. Employing bootscanning as an exploratory tool, we located several regions in the PLV genome that seem to have uncertain or conflicting phylogenetic histories. Phylogeny reconstruction based on distance and maximum-likelihood algorithms followed by a number of statistical tests confirms the existence of at least five putative recombinant fragments in the PLV genome with different clustering patterns. Split decomposition analysis also shows that phylogenetic relationships among PLVs may be better represented by network-based graphs, such as the ones produced by SplitsTree. Our findings not only imply that the six so-called pure PLV lineages have in fact mosaic genomes but also make more unlikely the hypothesis of cospeciation of SIVs and their simian hosts.