Most multicomponent high-entropy alloys (HEAs) are inevitably subject to losing ductility with increasing strength similar to conventional materials. Here, we controllably introduce a gradient nano-scaled dislocation-cell-structure in one stable single-phase Al0.1CoCrFeNi HEA, which results in significantly enhanced strength with exceptional ductility at ambient and at liquid nitrigen temperatures, and is superior to its counterparts with either homogeneous or heterogeneous structures. The sample-level structural-gradient structure with length scales spanning 6 orders of magnitude, the chemical features of the HEA and the nanoscaled dislocation cells with low-angle boundaries collectively contribute to a unique deformation mechanism associated with the formation of a high density of tiny stacking-faults and twins. Our findings offer a new promising pathway for improving the mechanical properties of materials through gradient dislocation structure.