The rapid evolution of extended-spectrum β-lactamases (ESBLs) represents a global health threat, undermining the efficacy of β-lactams, the most extensively used antibiotic class. To elucidate the evolutionary dynamics underlying β-lactam resistance, we constructed a comprehensive combinatorial mutant library comprising all 55,296 possible TEM-1 β-lactamase variants integrating 18 clinically observed mutations across 13 key residues. Over eight million empirical fitness measurements were obtained under selection pressure with both a native antibiotic substrate (ampicillin) and a novel antibiotic (aztreonam), establishing the largest experimentally determined fitness landscape for antibiotic resistance to date. Through graph-theoretic and epistatic analyses, we discovered that selection with ampicillin resulted in weak epistasis, with mutants rarely surpassing the fitness of the wild-type enzyme. Conversely, aztreonam selection elicited extensive higher-order epistasis, generating a rugged fitness landscape characterized by increased phenotypic unpredictability. Interpretable machine-learning analyses identified context-dependent epistatic interactions necessary for achieving high-level aztreonam resistance. Further evolutionary statistical analyses, including direct coupling analysis and latent generative landscapes, showed that top-performing TEM-1 variants consistently adhered to conserved epistatic patterns found in naturally occurring β-lactamases. Our findings demonstrate that higher-order epistasis critically shapes fitness landscape ruggedness when enzymes adapt to novel substrates, whereas adaptations to native substrates exhibit predictably smoother landscapes. This integrated experimental and computational framework provides a foundation for predictive evolutionary pharmacology, enabling assessments of newly developed β-lactams or emerging β-lactamase variants for their potential contribution to ESBL evolution. Importantly, incorporating graph-theoretically informed evolutionary constraints can strategically disrupt evolutionary pathways, presenting a viable approach to mitigate the rise of antibiotic resistance.