Human immunodeficiency virus type 1 (HIV-1) entry into target cells is mediated by the virus envelope binding to CD4 and the conformationally altered envelope subsequently binding to one of two chemokine receptors. HIV-1 envelope glycoprotein (gp120) has five variable loops, of which three (V1/V2 and V3) influence the binding of either CCR5 or CXCR4, the two primary coreceptors for virus entry. Minimal sequence changes in V3 are sufficient for changing coreceptor use from CCR5 to CXCR4 in some HIV-1 isolates, but more commonly additional mutations in V1/V2 are observed during coreceptor switching. We have modeled coreceptor switching by introducing most possible combinations of mutations in the variable loops that distinguish a previously identified group of CCR5- and CXCR4-using viruses. We found that V3 mutations entail high risk, ranging from major loss of entry fitness to lethality. Mutations in or near V1/V2 were able to compensate for the deleterious V3 mutations and may need to precede V3 mutations to permit virus survival. V1/V2 mutations in the absence of V3 mutations often increased the capacity of virus to utilize CCR5 but were unable to confer CXCR4 use. V3 mutations were thus necessary but not sufficient for coreceptor switching, and V1/V2 mutations were necessary for virus survival. HIV-1 envelope sequence evolution from CCR5 to CXCR4 use is constrained by relatively frequent lethal mutations, deep fitness valleys, and requirements to make the right amino acid substitution in the right place at the right time.