Carbon dioxide fixation is a polyphyletic trait that has evolved in widely separated prokaryotic branches. The three principal CO2-assimilation pathways are (i) the reductive pentose-phosphate cycle, i.e. the Calvin-Benson cycle; (ii) the reductive citric acid (or Arnon) cycle; and (iii) the net synthesis of acetyl-CoA from CO/CO2, or Wood pathway. Sequence analysis and the comparative biochemistry of these routes suggest that all of them were shaped to a considerable extent by the evolutionary recruitment of enzymes. Molecular phylogenetic trees show that the Calvin-Benson cycle was a relatively late development in the (eu)bacterial branch, suggesting that some form(s) of carbon assimilation may have been operative before chlorophyll-based photosynthesis. On the other hand, the ample phylogenetic distribution of both the Arnon and the Wood pathways does not allow us to infer which one of them is older. However, different lines of evidence, including experimental reports on the NiS/FeS-mediated C-C bond formation from CO and CH3SH are used here to argue that the first CO2-fixation route may have been a semi-enzymatic Wood-like pathway.