The development of high-performance structural and functional materials is vital in many industrial fields. High- and medium-entropy alloys (H/MEAs) with superior comprehensive properties owing to their specific microstructures are promising candidates for structural applications. More importantly, multitudinous efforts have been made to tailor the microstructures and regulate the properties of H/MEAs to further expand their industrial applications. The architectures of various heterostructures have enormous potential for the development of H/MEAs with outstanding performance. Herein, multiple heterogeneous structures with single and hierarchical heterogeneities are discussed in detail. Moreover, preparation methods for compositional inhomogeneity, bimodal structures, dual-phase structures, lamella/layered structures, harmonic structures (core-shell), multiscale precipitates and heterostructures coupled with specific microstructures in H/MEAs are also systematically reviewed. The deformation mechanisms induced by the different heterostructures are thoroughly discussed to explore the relationship between the heterostructures and the optimized properties of H/MEAs. The contributions of the heterostructures and advanced microstructures to the H/MEAs were comprehensively elucidated to further improve the properties of the alloys. Finally, this review discusses the future challenges of high-performance H/MEAs for industrial applications and provides feasible methods for optimizing heterostructures to enhance the comprehensive properties of H/MEAs.