Maturation of human immunodeficiency virus (HIV) depends on the processing of Gag and Pol polyproteins by the viral protease, making this enzyme a prime target for anti-HIV therapy. Among the protease substrates, the nucleocapsid-p1 (NC-p1) sequence is the least homologous, and its cleavage is the rate-determining step in viral maturation. In the other substrates of HIV-1 protease, P1 is usually either a hydrophobic or an aromatic residue, and P2 is usually a branched residue. NC-p1, however, contains Asn at P1 and Ala at P2. In response to the V82A drug-resistant protease mutation, the P2 alanine of NC-p1 mutates to valine (AP2V). To provide a structural rationale for HIV-1 protease binding to the NC-p1 cleavage site, we solved the crystal structures of inactive (D25N) WT and V82A HIV-1 proteases in complex with their respective WT and AP2V mutant NC-p1 substrates. Overall, the WT NC-p1 peptide binds HIV-1 protease less optimally than the AP2V mutant, as indicated by the presence of fewer hydrogen bonds and fewer van der Waals contacts. AlaP2 does not fill the P2 pocket completely; PheP1' makes van der Waals interactions with Val82 that are lost with the V82A protease mutation. This loss is compensated by the AP2V mutation, which reorients the peptide to a conformation more similar to that observed in other substrate-protease complexes. Thus, the mutant substrate not only binds the mutant protease more optimally but also reveals the interdependency between the P1' and P2 substrate sites. This structural interdependency results from coevolution of the substrate with the viral protease.