Timely administration of donor red blood cells (RBCs) is a crucial and life-saving procedure to restore tissue oxygenation in patients suffering from acute blood loss. However, important drawbacks of using allogenic RBCs are their limited availability and portability, specific storage requirements, short shelf life, or the need for blood type matching. These limitations result in serious logistical challenges that make the transfusion of donor RBCs difficult in extreme life-threatening situations prior to hospital admission. Thus, the engineering of hemoglobin (Hb) nanoparticles (Hb-NPs), which are free from the aforementioned limitations, has emerged as a promising strategy to create RBC substitutes to be used when donor blood is not available. Despite the tremendous progress achieved in recent years, many challenges still need to be overcome. For example, it is still difficult to create Hb-NPs with a high Hb content while also preventing the autoxidation of Hb into nonfunctional methemoglobin (metHb). Herein, the fabrication of small, solid Hb-NPs with an antioxidant coating is reported. By desolvation precipitation, Hb-NPs with an average hydrodynamic diameter of similar to 250 nm and a polydispersity index of similar to 0.2 are fabricated. A metal-phenolic network (MPN) layer consisting of a phenolic ligand (i.e., tannic acid) cross-linked through iron(III) ions is deposited onto the Hb-NPs surface to render antioxidant protection. The resulting MPN-coated Hb-NPs (MPN@Hb-NPs) maintain the ability of the encapsulated Hb to reversibly bind and release oxygen. The antioxidant properties are demonstrated, showing that MPN@Hb-NPs can effectively scavenge multiple reactive oxygen and nitrogen species, both in solution and in the presence of human RBCs and two relevant cell lines, namely, macrophages and endothelial cells. Importantly, these outstanding antioxidant properties resulting from the MPN translate into decreased metHb conversion. Finally, the newly reported MPN@Hb-NPs are also biocompatible, as shown by hemolysis rate and cell viability studies and can be used to protect the cells from oxidative damage. All in all, we have identified a novel strategy to minimize heme-mediated oxidative reactions that could potentially bring this new generation of Hb-based oxygen carriers a step closer to the clinic.