The picosecond geminate rebinding of molecular oxygen was monitored in a variety of different human, reptilian, and fish hemoglobins. The fast (100 to 200 picoseconds) component of the rebinding is highly sensitive to protein structure. Both proximal and distal perturbations of the heme affect this rebinding process. The rebinding yield for the fast process correlates with the frequency of the stretching motion of the iron-proximal histidine mode (VFe-His) observed in the transient Raman spectra of photodissociated ligated hemoglobins. The high-affinity R-state species exhibit the highest values for VFe-His and the highest yields for fast rebinding, whereas low affinity R-state species and T-state species exhibit lower values of VFe-His and correspondingly reduced yields for this geminate process. These findings link protein control of ligand binding with events at the heme.