We have recently observed promising success in a mouse model for treating the metabolic disorder phenylketonuria with phenylalanine ammonia lyase (PAL) from Rhodosporidium toruloides and Anabaena variabilis. Both molecules, however, required further optimization in order to overcome problems with protease susceptibility, thermal stability, and aggregation. Previously, we optimized PAL from R. toruloides, and in this case we reduced aggregation of the A. variabilis PAL by mutating two surface cysteine residues (C503 and C565) to serines. Additionally, we report the structural and biochemical characterization of the A. variabilis PAL C503S/C565S double mutant and carefully compare this molecule with the R. toruloides engineered PAL molecule. Unlike previously published PAL structures, significant electron density is observed for the two active-site loops in the A. variabilis C503S/C565S double mutant, yielding a complete view of the active site. Docking studies and N-hydroxysuccinimide-biotin binding studies support a proposed mechanism in which the amino group of the phenylalanine substrate is attacked directly by the 4-methylidene-imidazole-5-one prosthetic group. We propose a helix-to-loop conformational switch in the helices flanking the inner active-site loop that regulates accessibility of the active site. Differences in loop stability among PAL homologs may explain the observed variation in enzyme efficiency, despite the highly conserved structure of the active site. A. variabilis C503S/C565S PAL is shown to be both more thermally stable and more resistant to proteolytic cleavage than R. toruloides PAL. Additional increases in thermal stability and protease resistance upon ligand binding may be due to enhanced interactions among the residues of the active site, possibly locking the active-site structure in place and stabilizing the tetramer. Examination of the A. variabilis C503S/C565S PAL structure, combined with analysis of its physical properties, provides a structural basis for further engineering of residues that could result in a better therapeutic molecule.