Amino acid substitutions in human immunodeficiency virus type 1 (HIV-1) Gag cleavage sites have been identified in HIV-1 isolated from patients with AIDS failing chemotherapy containing protease inhibitors (PIs). However, a number of highly PI-resistant HIV-1 variants lack cleavage site amino acid substitutions. In this study we identified multiple novel amino acid substitutions including L75R, H219Q, V390D/V390A, R409K, and E468K in the Gag protein at non-cleavage sites in common among HIV-1 variants selected against the following four PIs: amprenavir, JE-2147, KNI-272, and UIC-94003. Analyses of replication profiles of various mutant clones including competitive HIV-1 replication assays demonstrated that these mutations were indispensable for HIV-1 replication in the presence of PIs. When some of these mutations were reverted to wild type amino acids, such HIV-1 clones failed to replicate. However, virtually the same Gag cleavage pattern was seen, indicating that the mutations affected Gag protein functions but not their cleavage sensitivity to protease. These data strongly suggest that non-cleavage site amino acid substitutions in the Gag protein recover the reduced replicative fitness of HIV-1 caused by mutations in the viral protease and may open a new avenue for designing PIs that resist the emergence of PI-resistant HIV-1.