Conventional polycrystalline metals become stronger with decreasing grain size, yet softening starts to take over at the nanometer regime, giving rise to the strongest size at which the predominate strengthening mechanism switches to softening. We show that this critical size for the onset of softening can be tuned by tailoring grain size gradient, and raising in the gradient shifts the size toward the smaller value. The decrease in the strongest size is prompted by mitigation of grain boundary-mediated softening processes accompanying by enhanced intragranular plastic deformations. We found that the nanograins smaller than 6 nm, mainly involving intergranular sliding in homogeneous structures, reveal anomalous plastic deformation in gradient systems, which is mediated by partial dislocation nucleation, faulting and twinning activated in a gradient stress field. The results on extended dislocation slip and gradient plasticity, stemming from the structure heterogeneity, shed light on an emerging class of heterogeneous nanostructured materials of improved strength-ductility synergy.