Phenylketonuria (PKU) is a genetic disease characterized by the inability to convert dietary phenylalanine to tyrosine by phenylalanine hydroxylase. Given the importance of gut microbes in digestion, a genetically engineered microbe could potentially degrade some ingested phenylalanine from the diet prior to absorption. To test this, a phenylalanine lyase gene from Anabaena variabilis (AvPAL) was codon-optimized and cloned into a shuttle vector for expression in Lactobacillus reuteri 100-23C (pHENOMMenal). Functional expression of AvPAL was determined in vitro, and subsequently tested in vivo in homozygous PAHenu2 (PKU model) mice. Initial trials of two PAHenu2 homozygous (PKU) mice defined conditions for freeze-drying and delivery of bacteria. Animals showed reduced blood phe within three to four days of treatment with pHENOMMenal probiotic, and blood phe concentrations remained significantly reduced (P < 0.0005) compared to untreated controls during the course of experiments. Although pHENOMMenal probiotic could be cultured from fecal samples at four months post treatment, it could no longer be cultivated from feces at eight months post treatment, indicating eventual loss of the microbe from the gut. Preliminary screens during experimentation found no immune response to AvPAL. Collectively these studies provide data for the use of a genetically engineered probiotic as a potential treatment for PKU.