Metabolic network rewiring is the rerouting of metabolism through the use of alternate enzymes to adjust pathway flux and accomplish specific anabolic or catabolic objectives. Here, we report the first characterization of two parallel pathways for the breakdown of the short chain fatty acid propionate in Caenorhabditis elegans. Using genetic interaction mapping, gene co-expression analysis, pathway intermediate quantification and carbon tracing, we uncover a vitamin B12-independent propionate breakdown shunt that is transcriptionally activated on vitamin B12 deficient diets, or under genetic conditions mimicking the human diseases propionic- and methylmalonic acidemia, in which the canonical B12-dependent propionate breakdown pathway is blocked. Our study presents the first example of transcriptional vitamin-directed metabolic network rewiring to promote survival under vitamin deficiency. The ability to reroute propionate breakdown according to B12 availability may provide C. elegans with metabolic plasticity and thus a selective advantage on different diets in the wild.