One fundamental goal of current research is to understand how complex biomolecular networks took the form that we observe today. Cellular metabolism is probably one of the most ancient biological networks and constitutes a good model system for the study of network evolution. While many evolutionary models have been proposed, a substantial body of work suggests metabolic pathways evolve fundamentally by recruitment, in which enzymes are drawn from close or distant regions of the network to perform novel chemistries or use different substrates. Here we review how structural and functional genomics has impacted our knowledge of evolution of modern metabolism and describe some approaches that merge evolutionary and structural genomics with advances in bioinformatics. These include mining the data on structure and function of enzymes for salient patterns of enzyme recruitment. Initial studies suggest modern metabolism originated in enzymes of nucleotide metabolism harboring the P-loop hydrolase fold, probably in pathways linked to the purine metabolic subnetwork. This gateway of recruitment gave rise to pathways related to the synthesis of nucleotides and cofactors for an ancient RNA world. Once the TIM beta/alpha-barrel fold architecture was discovered, it appears metabolic activities were recruited explosively giving rise to subnetworks related to carbohydrate and then amino acid metabolism. Remarkably, recruitment occurred in a layered system reminiscent of Morowitz's prebiotic shells, supporting the notion that modern metabolism represents a palimpsest of ancient metabolic chemistries.