Aluminum alloys have been widely used in fields such as automotive and aerospace industries, owing to their excellent mechanical properties, lightweight, and low recycling costs. However, aluminum alloys processed by selective laser melting (SLM) typically suffer from insufficient strength and fracture toughness. To tackle this issue, a new strategy that integrates eutectic composition design and grain refinement has been adopted to create a heterogeneous structure that can improve strength and toughness of SLMed Al-Fe-Zr alloys. The SLMed AlFe5 alloy consists of high-volume-fraction of coarse and columnar grains and low-volume-fraction of fine grains, and no obvious heterogeneity is visible across the microstructure length scale. With the addition of Zr, the volume fraction of fine grains significantly increases, leading to the heterogeneous distribution of coarse and fine grains in the SLMed AlFe5Zr1 alloy. Meanwhile, both AlFe5 and AlFe5Zr1 alloys show a nanoscale cellular structure. This type of a nanosized cellular structure, together with supersaturated Fe and high-density dislocations, contributes to a high yield strength of 400 MPa for the SLMed AlFeZr alloys. The heterogeneous structure can further improve the strain strengthening capability, enabling a tensile strength as high as 450 MPa for the AlFe5Zr1 alloy. Furthermore, the heterogeneous structure promotes crack deflection and crack tip blunting, which can effectively increase crack growth resistance and impart superior fracture toughness to the AlFe5Zr1 alloy.