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 materials. More importantly, multitudinous efforts have been made to regulate the microstructures and the properties of H/MEAs to further expand their industrial applications. The various heterostructures have enormous potential for the development of H/MEAs with outstanding performance. Herein, multiple heterogeneous structures with single and hierarchical heterogeneities were 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 were also systematically reviewed. The deformation mechanisms induced by the different heterostructures were 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 discussed 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.