Fitness epistasis, the interaction among alleles at different loci in their effects on fitness, has potentially important consequences for adaptive evolution. We investigated fitness epistasis among amino acids of a functionally important region of the human immunodeficiency virus type 1 (HIV-1) exterior envelope glycoprotein (gp120). Seven mutations putatively involved in the adaptation of the second conserved to third variable protein region (C2-V3) to the use of an alternative host-cell chemokine coreceptor (CXCR4) for cell entry were engineered singly and in combinations on the wild-type genetic background and their effects on viral infectivity were measured. Epistasis was found to be common and complex, involving not only pairwise interactions, but also higher-order interactions. Interactions could also be surprisingly strong, changing fitness by more than 9 orders of magnitude, which is explained by some single mutations being practically lethal. A consequence of the observed epistasis is that many of the minimum-length mutational trajectories between the wild type and the mutant with highest fitness on cells expressing the alternative coreceptor are selectively inaccessible. These results may help explain the difficulty of evolving viruses that use the alternative coreceptor in culture and the delayed evolution of this phenotype in natural infection. Knowledge of common, complex, and strong fitness interactions among amino acids is necessary for a full understanding of protein evolution.