Low nutrient and energy availability has led to the evolution of numerous strategies for overcoming these limitations, of which symbiotic associations represent a key mechanism. Particularly striking are the associations between chemosynthetic bacteria and marine animals that thrive in nutrient-poor environments such as the deep sea because the symbionts allow their hosts to grow on inorganic energy and carbon sources such as sulfide and CO(2). Remarkably little is known about the physiological strategies that enable chemosynthetic symbioses to colonize oligotrophic environments. In this study, we used metaproteomics and metabolomics to investigate the intricate network of metabolic interactions in the chemosynthetic association between Olavius algarvensis, a gutless marine worm, and its bacterial symbionts. We propose previously undescribed pathways for coping with energy and nutrient limitation, some of which may be widespread in both free-living and symbiotic bacteria. These pathways include (i) a pathway for symbiont assimilation of the host waste products acetate, propionate, succinate and malate; (ii) the potential use of carbon monoxide as an energy source, a substrate previously not known to play a role in marine invertebrate symbioses; (iii) the potential use of hydrogen as an energy source; (iv) the strong expression of high-affinity uptake transporters; and (v) as yet undescribed energy-efficient steps in CO(2) fixation and sulfate reduction. The high expression of proteins involved in pathways for energy and carbon uptake and conservation in the O. algarvensis symbiosis indicates that the oligotrophic nature of its environment exerted a strong selective pressure in shaping these associations.