In conventional metallic materials, strength and ductility are mutually exclusive, referred to as strength-ductility trade-off. Here, we demonstrate an approach to improve the strength and ductility simultaneously by introducing micro-banding and the accumulation of a high density of dislocations in single-phase high-entropy alloys (HEAs). We prepare two compositions (Cr₁₀Mn₅₀Fe₂₀Co₁₀Ni₁₀ and Cr₁₀Mn₁₀Fe₆₀Co₁₀Ni₁₀) with distinctive different stacking fault energies (SFEs) as experimental materials. The strength and ductility of the Cr₁₀Mn₅₀Fe₂₀Co₁₀Ni₁₀ HEA are improved concurrently by grain refinement from 347.5 ± 216.1 µm to 18.3 ± 9.3 µm. The ultimate tensile strength increases from 543 ± 4 MPa to 621 ± 8 MPa and the elongation to failure enhances from 43±2% to 55±1%. To reveal the underlying deformation mechanisms responsible for such a strength-ductility synergy, the microstructural evolution upon loading is investigated by electron microscopy techniques. The dominant deformation mechanism observed for the Cr₁₀Mn₅₀Fe₂₀Co₁₀Ni₁₀ HEA is the activation of micro-bands, which act both as dislocation sources and dislocation barriers, eventually, leading to the formation of dislocation cell structures. By decreasing grain size, much finer dislocation cell structures develop, which are responsible for the improvement in work hardening rate at higher strains (>7%) and thus for the increase in both strength and ductility. In order to drive guidelines for designing advanced HEAs by tailoring their SFE and grain size, we compute the SFEs of Cr₁₀Mn_xFe_70–xCo₁₀Ni10 (10 ≤ x ≤ 60) based on first principles calculations. Based on these results the overall changes on deformation mechanism can be explained by the influence of Mn on the SFE.