The potential of the frequently encountered (βα)8-barrel fold to acquire new functions was tested by an approach combining random mutagenesis and selection in vivo. For this purpose, the genes encoding 52 different phosphate-binding (βα)8-barrel proteins were subjected to error-prone PCR and cloned into an expression plasmid. The resulting mixed repertoire was used to transform different auxotrophic Escherichia coli strains, each lacking an enzyme with a phosphate-containing substrate. After plating of the different transformants on minimal medium, growth was observed only for two strains, lacking either the gene for the serine phosphatase SerB or the phosphoserine aminotransferase SerC. The same mutants of the E. coli genes nanE (encoding a putative N-acetylmannosamine-6-phosphate 2-epimerase) and pdxJ (encoding the pyridoxine 5'-phosphate synthase) were responsible for rescuing both ΔserB and ΔserC. Unexpectedly, the complementing NanE and PdxJ variants did not catalyze the SerB or SerC reactions in vitro. Instead, RT-qPCR, RNAseq, and transcriptome analysis showed that they rescue the deletions by enlisting the help of endogenous E. coli enzymes HisB and HisC through exclusive up-regulation of histidine operon transcription. While the promiscuous SerB activity of HisB is well-established, our data indicate that HisC is promiscuous for the SerC reaction, as well. The successful rescue of ΔserB and ΔserC through point mutations and recruitment of additional amino acids in NanE and PdxJ provides another example for the adaptability of the (βα)8-barrel fold.