All plants contain hemoglobins that fall into distinct phylogenetic classes. The subset of plants that carry out symbiotic nitrogen fixation expresses hemoglobins that scavenge and transport oxygen to bacterial symbiotes within root nodules. These "symbiotic" oxygen transport hemoglobins are distinct in structure and function from the nonoxygen transport ("nonsymbiotic") Hbs found in all plants. Hemoglobins found in two closely related plants present a paradox concerning hemoglobin structure and function. Parasponia andersonii is a nitrogen-fixing plant that expresses a symbiotic hemoglobin (ParaHb) characteristic of oxygen transport hemoglobins in having a pentacoordinate ferrous heme iron, moderate oxygen affinity, and a relatively rapid oxygen dissociation rate constant. A close relative that does not fix nitrogen, Trema tomentosa, expresses hemoglobin (TremaHb) sharing 93% amino acid identity to ParaHb, but its phylogeny predicts a typical nonsymbiotic hemoglobin with a hexacoordinate heme iron, high oxygen affinity, and slow oxygen dissociation rate constant. Here we characterize heme coordination and oxygen binding in TremaHb and ParaHb to investigate whether or not two hemoglobins with such high sequence similarity are actually so different in functional behavior. Our results indicate that the two proteins resemble nonsymbiotic hemoglobins in the ferric oxidation state and symbiotic hemoglobins in the ferrous oxidation state. They differ from each other only in oxygen affinity and oxygen dissociation rate constants, two factors key to their different functions. These results demonstrate distinct mechanisms for convergent evolution of oxygen transport in different phylogenetic classes of plant hemoglobins.