Despite the major role of Gag in establishing resistance of HIV-1 to protease inhibitors (PIs), very limited data are available on the total contribution of Gag residues to resistance to PIs. To identify in detail Gag residues and structural interfaces associated with the development of HIV-1 resistance to PIs, we traced viral evolution under the pressure of PIs using Gag-protease single genome sequencing and coevolution analysis of protein sequences in 4 patients treated with PIs over a 9-year period. We identified a total of 38 Gag residues correlated with the protease, 32 of which were outside Gag cleavage sites. These residues were distributed in 23 Gag-protease groups of coevolution, with the viral matrix and the capsid represented in 87% and 52% of the groups. In addition, we uncovered the distribution of Gag correlated residues in specific protein surfaces of the inner face of the viral matrix and at the Cyclophilin A binding loop of the capsid. In summary, our findings suggest a tight interdependency between Gag structural proteins and the protease during the development of resistance of HIV-1 to PIs.