Deep mutational scanning (DMS) has recently emerged as a powerful method to study protein sequence-function relationships but is not well-explored as a guide to enzyme engineering and identifying of pathways by which their catalytic cycle may be improved. We report such a demonstration in this work using a phenylalanine ammonia-lyase (PAL), which deaminates L-phenylalanine to trans-cinnamic acid and has widespread application in chemoenzymatic synthesis, agriculture, and medicine. In particular, the PAL from Anabaena variabilis (AvPAL*) has garnered significant attention as the active ingredient in Pegvaliase, the only FDA-approved drug for treating classical phenylketonuria (PKU). Although an extensive body of literature exists on the structure, substrate-specificity, and catalytic cycle, protein-wide sequence determinants of function remain unknown, as do intermediate reaction steps that limit turnover frequency, which has hindered the rational engineering of these enzymes. Here, we created a detailed sequence-function landscape of AvPAL* by performing DMS and revealed 112 mutations at 79 functionally relevant sites that affect a positive change in enzyme fitness. Using fitness values and structure-function analysis, we picked a subset of positions for comprehensive single- and multi-site saturation mutagenesis and identified combinations of mutations that led to improved reaction kinetics in cell-free and cellular contexts. We then performed quantum mechanics/molecular mechanics (QM/MM) and molecular dynamics (MD) studies to understand the mechanistic role of the most beneficial mutations and observed that different mutants confer improvements via different mechanisms, including stabilizing transition and intermediate states, improving substrate diffusion into the active site, and decreasing product inhibition. This work demonstrates how DMS can be combined with computational analysis to effectively identify significant mutations that enhance enzyme activity along with the underlying mechanisms by which these mutations confer their benefit.