Protease inhibitors (PIs) are the second- and last-line therapy for the majority of HIV-infected patients worldwide. Only around 20% of individuals who fail PI regimens develop major resistance mutations in protease. We sought to explore the role of mutations in gag-pro genotypic and phenotypic changes in viruses from six Nigerian patients who failed PI-based regimens without known drug resistance-associated protease mutations in order to identify novel determinants of PI resistance. Target enrichment and next-generation sequencing (NGS) with the Illumina MiSeq system were followed by haplotype reconstruction. Full-length Gag-protease gene regions were amplified from baseline (pre-PI) and virologic failure (VF) samples, sequenced, and used to construct gag-pro-pseudotyped viruses. Phylogenetic analysis was performed using maximum-likelihood methods. Susceptibility to lopinavir (LPV) and darunavir (DRV) was measured using a single-cycle replication assay. Western blotting was used to analyze Gag cleavage. In one of six participants (subtype CRF02_AG), we found 4-fold-lower LPV susceptibility in viral clones during failure of second-line treatment. A combination of four mutations (S126del, H127del, T122A, and G123E) in the p17 matrix of baseline virus generated a similar 4-fold decrease in susceptibility to LPV but not darunavir. These four amino acid changes were also able to confer LPV resistance to a subtype B Gag-protease backbone. Western blotting demonstrated significant Gag cleavage differences between sensitive and resistant isolates in the presence of drug. Resistant viruses had around 2-fold-lower infectivity than sensitive clones in the absence of drug. NGS combined with haplotype reconstruction revealed that resistant, less fit clones emerged from a minority population at baseline and thereafter persisted alongside sensitive fitter viruses. We used a multipronged genotypic and phenotypic approach to document emergence and temporal dynamics of a novel protease inhibitor resistance signature in HIV-1 matrix, revealing the interplay between Gag-associated resistance and fitness.