Tyrosine phenol-lyase (TPL) is a useful enzyme for the synthesis of pharmaceutical aromatic amino acids. In the current study, sequential DNA shuffling and screening were used to enhance the stability of TPL. Twenty-thousand mutants were screened, and several improved variants were isolated. One variant named A13V, in which the $13^{th}$ amino acid alanine was substituted by valine, exhibited a higher temperature and denaturant stability than the wild-type TPL. The purified mutant TPL, A13V, retained about 60% of its activity at $76^circ{C}$, whereas the activity of the wild-type TPL decreased to less than 20% at the same temperature. Plus, A13V exhibited about 50% activity with 3 M urea, while the wild-type TPL lost almost all its catalytic activity, indicating an increased denaturant tolerance in the mutant A13V. It is speculated that the substitution of Val for the Ala in the $eta$-strand of the N-terminal arm was responsible for the heightened stabilization, and that the current results will contribute to further research on the structural stability of TPL.