Edwardsiella ictaluri is a Gram-negative facultative intracellular rod, causing enteric septicemia of catfish (ESC). Several heme uptake systems have been described in bacterial pathogens, most of which involve outer membrane proteins (OMPs). We have shown recently that heme/hemoglobin receptor family protein (HemR) is significantly up-regulated in E. ictaluri under iron-restricted conditions. In this work, our goal was to construct E. ictaluri HemR mutants and assess their virulence and immune protection potentials in catfish. To accomplish this, an in-frame deletion mutant (EiΔhemR) was constructed, and its virulence and immune protection were determined in catfish fingerlings and fry. The results indicated that the EiΔhemR was attenuated completely in catfish fingerlings, but it was virulent in 14 day-old catfish fry. To increase the attenuation of EiΔhemR in fry, we introduced frdA and sdhC gene deletions to the mutant, yielding two double (EiΔhemRΔfrdA and EiΔhemRΔsdhC) and one triple (EiΔhemRΔfrdAΔsdhC) mutants. Results indicated that two double HemR mutants did not exhibit increased attenuation, but the triple HemR mutant showed significantly less virulence and high protection in fry (p < 0.05). Histological examination of fry tissues vaccinated with the triple mutant displayed similar inflammation to that of wild-type infected fry, but much less necrosis and far fewer bacteria were observed. Immunohistochemistry (IHC) result indicated fewer numbers of bacteria around blood vessel and in the hematopoietic tissue in fry infected with triple mutant compared to control group infected with E. ictaluri wild-type. Our data indicated that EiΔhemR was safe and protective in catfish fingerlings, while EiΔhemRΔfrdAΔsdhC was much safer in catfish fry.