Bacteria adapt to changing environments by rewiring their metabolism to synthesize or scavenge essential biomolecules. When a key nutrient becomes unavailable, or a genetic mutation disrupts its production, evolving an alternative metabolic pathway may be required to restore growth. The first step in evolution of a new metabolic pathway is recruitment of enzymes with weak, secondary “promiscuous” activities to serve new catalytic functions. Recruited enzymes are typically inefficient in their new roles, so bacteria may acquire more genetic mutations over time to improve recruited enzyme activity and increase flux through the evolving protopathway. We developed a model system to study how protopathways evolve. In Escherichia coli, synthesis of the essential cofactor pyridoxal 5'-phosphate (PLP; vitamin B6) requires the enzyme PdxB. We deleted the gene encoding PdxB, blocking PLP synthesis, then subjected these cells to adaptive laboratory evolution in minimal medium containing either 0.2% or 0.4% glucose. In both conditions, populations regained the ability to produce PLP, but via distinct evolutionary solutions. All lineages evolved in 0.2% glucose appear to have repurposed a single enzyme, SerA, to replace PdxB. In 0.4% glucose, most lineages evolved a four-step protopathway assembled from the promiscuous activities of four enzymes. These results show that nutrient availability can shape which evolutionary paths are accessible, influencing whether adaptation proceeds through modification of a single enzyme or assembly of a multi-step pathway.