APOBEC3 genes encode cytidine deaminases endowed with the ability to inhibit retroviruses and retrotransposons. These genes have been targets of natural selection throughout primate evolutionary history. We analysed their selection pattern in human populations observing that APOBEC3F and 3G are neutrally evolving. Conversely, nucleotide diversity was extremely high for APOBEC3H, and most tests rejected the hypothesis of selective neutrality in Eurasian populations. Haplotype analysis and the derived intra-allelic nucleotide diversity test indicated that positive selection has driven the increase in frequency of one haplotype (Hap I) outside Africa. Consistently, population genetic differentiation between African and non-African populations was higher than expected under neutrality. A case/control association analysis indicated that Hap I is associated with protection from sexually transmitted HIV-1 infection. Hap I carries a protein-destabilizing variant and a residue conferring resistance to Vif-mediated degradation. Data herein suggest that lower protein stability might have been traded-off with a higher ability to circumvent Vif-mediated hijacking. Alternatively, transcription regulatory variants might represent the selection target. Our data represent an example of how the selective pressures exerted by extinct or unknown viral agents can be exploited to provide valuable information on the allelic determinants of susceptibility to modern infections.