In order to proliferate and mount an infection, many bacterial pathogens need to acquire iron from their host. The most abundant iron source in the body is the oxygen transporter hemoglobin (Hb). Streptococcus pyogenes, a potentially lethal human pathogen, uses the Shr protein to capture Hb on the cell surface. Shr is an important virulence factor, yet the mechanism by which it captures Hb and acquires its heme is not well-understood. Here, we show using NMR and biochemical methods that Shr binds Hb using two related modules that were previously defined as domains of unknown function (DUF1533). These hemoglobin-interacting domains (HIDs), called HID1 and HID2, are autonomously folded and independently bind Hb. The 1.5 Å resolution crystal structure of HID2 revealed that it is a structurally unique Hb-binding domain. Mutagenesis studies revealed a conserved tyrosine in both HIDs that is essential for Hb binding. Our biochemical studies indicate that HID2 binds Hb with higher affinity than HID1 and that the Hb tetramer is engaged by two Shr receptors. NMR studies reveal the presence of a third autonomously folded domain between HID2 and a heme-binding NEAT1 domain, suggesting that this linker domain may position NEAT1 near Hb for heme capture.