Tetrahydrobiopterin-dependent hydroxylation of aromatic amino acids is the first step in the biosynthesis of many neuroactive compounds in humans. A fundamental challenge in building these pathways in Escherichia coli is the provision of the non-native hydroxylase cofactor, tetrahydrobiopterin. To solve this, we designed a genetic selection that relies on the tyrosine synthesis activity of phenylalanine hydroxylase. Using adaptive laboratory evolution, we demonstrate the use of this selection to discover: (1) a minimum set of heterologous enzymes and a host folE (T198I) mutation for achieving this type of hydroxylation chemistry in whole cells, (2) functional complementation of tetrahydrobiopterin by indigenous cofactors, and (3) a tryptophan hydroxylase mutation for improving protein abundance. Thus, the goal of having functional aromatic-amino-acid hydroxylation in E. coli was achieved through directed metabolic pathway evolution.