Several human APOBEC3 deaminases can inhibit HIV-1 replication in vitro. HIV-1 Vif counteracts this restriction by targeting APOBEC3 for proteasomal degradation. Human APOBEC3H (A3H) is highly polymorphic, with natural variants differing considerably in anti-HIV-1 activity in vitro. To examine HIV-1 adaptation to variation in A3H activity in a natural infection context, we determined the A3H haplotypes and Vif sequences from 76 recently infected HIV-1 patients. We detected A3H-specific Vif changes suggesting viral adaptation. The patient-derived Vif sequences were used to engineer viruses that specifically differed in their ability to counteract A3H. Replication of these Vif-variant viruses in primary T cells naturally expressing active or inactive A3H haplotypes showed that endogenously expressed A3H restricts HIV-1 replication. Proviral DNA from A3H-restricted viruses showed high levels of G-to-A mutations in an A3H-specific GA dinucleotide context. Taken together, our data validate A3H expressed at endogenous levels as a bona fide HIV-1 restriction factor.