Here, a new strategy for designing heterogeneous medium-entropy alloys with light-weight and excellent mechanical properties is proposed. Alx(CuFeMn)100-x (x = 0, 7.5, and 15 at%) alloys were developed by utilizing the immiscible nature of CuFe alloys. The microstructures of the alloys show phase separation into Curich and Fe-rich regions, and the addition of Al transforms the crystal structure from dual face-centered cubic to face-centered cubic and body-centered cubic. Phase separation of the microstructure into two domains enables further dissolution of Al into the matrix. The alloys exhibit high strength because of solid solution strengthening and hetero-deformation induced strengthening caused by heterogeneous microstructures. The presence of nano-scale twins and essential partially recrystallized microstructures also enhances the strength of the alloys. This new type of medium-entropy alloys is expected to expand the design window in physical metallurgy.