We isolated and sequenced two haemoglobin genes from the early-branching angiosperm Euryale ferox (Nymphaeaceae). The two genes belong to the two known classes of plant haemoglobin. Their existence in Nymphaeaceae supports the theory that class 1 haemoglobin was ancestrally present in all angiosperms, and is evidence for class 2 haemoglobin being widely distributed. These sequences allowed us to unambiguously root the angiosperm haemoglobin phylogeny, and to corroborate the hypothesis that the class 1/class 2 duplication event occurred before the divergence between monocots and eudicots. We addressed the molecular evolution of plant haemoglobin by comparing the synonymous and nonsynonymous substitution rates in various groups of genes. Class 2 haemoglobin genes of legumes (functionally involved in a symbiosis with nitrogen-fixing bacteria) show a higher nonsynonymous substitution rate than class 1 (nonsymbiotic) haemoglobin genes. This suggests that a change in the selective forces applying to plant haemoglobins has occurred during the evolutionary history of this gene family, potentially in relation with the evolution of symbiosis.