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 -structured nanoprecipitates ranging from several to hundreds of nanometers. The heterogeneous L1 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.