Syntrophy allows a microbial community as a whole to survive in an environment, even though individual microbes cannot. The metabolic interdependence typical of syntrophy is thought to arise from the accumulation of degenerative mutations during the sustained co-evolution of initially self-sufficient organisms. An alternative and underexplored possibility is that syntrophy can emerge spontaneously in communities of organisms that did not co-evolve. Here, we study this de novo origin of syntrophy using experimentally validated computational techniques to predict an organism's viability from its metabolic reactions. We show that pairs of metabolisms that are randomly sampled from a large space of possible metabolism and viable on specific primary carbon sources often become viable on new carbon sources by exchanging metabolites. The same biochemical reactions that are required for viability on primary carbon sources also confer viability on novel carbon sources. Our observations highlight a new and important avenue for the emergence of metabolic adaptations and novel ecological interactions.