A composite of two different medium entropy alloys (MEAs, i.e., CoCrFeNi and AlCoCrFe) was synthesized using ball milling and spark plasma sintering. The composite microstructure contains a homogenous distribution of fcc and bcc phases with submicron-sized grains and exhibits excellent microstructural and phase stability even after 100 h heat treatment at 800 °C. The composite provides a combination of high compressive strength, adequate plastic strain, and multiple strain-hardening stages at room temperature. This first exploratory study on a MEA composite can be used as a template to other systems and illustrates the feasibility of combining two or more MEAs. © 2020 Acta Materialia Inc.