Abstract Alloys with ultra-high strength and sufficient ductility are highly desired for modern engineering applications but difficult to develop. Here we report that, by a careful controlling alloy composition, thermomechanical process, and microstructural feature, a Co-Cr-Ni-based medium-entropy alloy (MEA) with a dual heterogeneous structure of both matrix and precipitates can be designed to provide an ultra-high tensile strength of 2.2 GPa and uniform elongation of 13% at ambient temperature, properties that are much improved over their counterparts without the heterogeneous structure. Electron microscopy characterizations reveal that the dual heterogeneous structures are composed of a heterogeneous matrix with both coarse grains (10∼30 μm) and ultra-fine grains (0.5∼2 μm), together with heterogeneous L1 2 -structured nanoprecipitates ranging from several to hundreds of nanometers. The heterogeneous L1 2 nanoprecipitates are fully coherent with the matrix, minimizing the elastic misfit strain of interfaces, relieving the stress concentration during deformation, and playing an active role in enhanced ductility.