Display omitted •A crystalline-amorphous nanostructured top surface layer is developed on a high-entropy alloy by laser surface processing.•The phase decomposition-mediated mechanisms forming the crystalline-amorphous nanostructured surface layer are uncovered.•Localized micro-pillar compression tests on surface layer shows an ultrahigh yield strength and a good compression strain .•The co-deformation cooperative actions include dislocation activities in nanograins but crystallization in amorphous GBs.•The co-deformation cooperative effects subsequently lead to the grain coarsening via GB-mediated plasticity. Heterogeneous crystalline-amorphous nanostructures have been documented to show superior strength-ductility synergy via the co-deformation cooperative effects of nanograins and amorphous grain boundaries. In this work, a facile laser surface remelting technique with rapid cooling rate was successfully developed to fabricate a ∼ 100 μm-thick gradient nanostructured layer accompanied by phase decomposition on a TiZrHfTaNb0.2 high-entropy alloy, where a ∼ 5 μm-thick crystalline-amorphous nanostructured top surface layer with an average grain size of ∼ 7 nm was obtained. Such crystalline-amorphous nanostructured layer shows an ultrahigh yield strength of ∼ 6.0 GPa and a compression strain of ∼ 25 % during the localized micro-pillar compression tests. The atomic observations reveal that co-deformation cooperative mechanisms include the well-retained dislocation activities in nanograins but crystallization in amorphous grain boundaries, which subsequently lead to the grain coarsening via grain boundary-mediated plasticity. This study sheds light on the development of high-performance high-entropy alloys with novel crystalline-amorphous nanostructures and provides significant insight into their plastic deformation mechanisms.