Haemoglobin has previously been recorded in plants only in the nitrogen-fixing nodules formed by symbiotic association between Rhizobium or Frankia and legume or non-legume hosts. Structural similarities amongst these and animal haemoglobins at the protein and gene level suggested a common evolutionary origin. This suggests that haemoglobin genes, inherited from an ancestor common to plants and animals, might be present in all plants. We report here the isolation of a haemoglobin gene from Trema tomentosa, a non-nodulating relative of Parasponia (Ulmaceae). The gene has three introns located at positions identical to those in the haemoglobin genes of nodulating plant species, strengthening the case for a common origin of all plant haemoglobin genes. The data argue strongly against horizontal haemoglobin gene transfer from animals to plants. The Trema gene has a tissue-specific pattern of transcription and translation, producing monomeric haemoglobin in Trema roots. We have also found that the Parasponia haemoglobin gene is transcribed in roots of non-nodulated plants. These results suggest that haemoglobin has a role in the respiratory metabolism of root cells of all plant species. We propose that its special role in nitrogen-fixing nodules has required adaptation of the haemoglobin-gene regulation pathway, to give high expression in the specialized environment of the nodule.