Cellular restriction factors, which render cells intrinsically resistant to viruses, potentially impose genetic barriers to cross-species transmission and emergence of viral pathogens in nature. One such factor is APOBEC3G. To overcome APOBEC3G-mediated restriction, many lentiviruses encode Vif, a protein that targets APOBEC3G for degradation. As with many restriction factor genes, primate APOBEC3G displays strong signatures of positive selection. This is interpreted as evidence that the primate APOBEC3G locus reflects a long-term evolutionary "arms-race" between retroviruses and their primate hosts. Here, we provide direct evidence that APOBEC3G has functioned as a barrier to cross-species transmission, selecting for viral resistance during emergence of the AIDS-causing pathogen SIVmac in captive colonies of Asian macaques in the 1970s. Specifically, we found that rhesus macaques have multiple, functionally distinct APOBEC3G alleles, and that emergence of SIVmac and simian AIDS required adaptation of the virus to evade APOBEC3G-mediated restriction. Our evidence includes the first comparative analysis of APOBEC3G polymorphism and function in both a reservoir and recipient host species (sooty mangabeys and rhesus macaques, respectively), and identification of adaptations unique to Vif proteins of the SIVmac lineage that specifically antagonize rhesus APOBEC3G alleles. By demonstrating that interspecies variation in a known restriction factor selected for viral counter-adaptations in the context of a documented case of cross-species transmission, our results lend strong support to the evolutionary "arms-race" hypothesis. Importantly, our study confirms that APOBEC3G divergence can be a critical determinant of interspecies transmission and emergence of primate lentiviruses, including viruses with the potential to infect and spread in human populations.