Materials containing heterogeneous nanostructures hold great promise for achieving superior mechanical properties. However, the strengthening effect due to plastically inhomogeneous deformation in heterogeneous nanostructures has not been clearly understood. Here, we investigate a prototypical heterogeneous nanostructured material of gradient nanotwinned (GNT) Cu to unravel the origin of its extra strength arising from gradient nanotwin structures relative to uniform nanotwin counterparts. We measure the back and effective stresses of GNT Cu with different nanotwin thickness gradients and compare them with those of homogeneous nanotwinned Cu with different uniform nanotwin thicknesses. We find that the extra strength of GNT Cu is caused predominantly by the extra back stress resulting from nanotwin thickness gradient, while the effective stress is almost independent of the gradient structures. The combined experiment and strain gradient plasticity modeling show that an increasing structural gradient in GNT Cu produces an increasing plastic strain gradient, thereby raising the extra back stress. The plastic strain gradient is accommodated by the accumulation of geometrically necessary dislocations inside an unusual type of heterogeneous dislocation structure in the form of bundles of concentrated dislocations. Such a heterogeneous dislocation structure produces microscale internal stresses leading to the extra back stress in GNT Cu. Altogether, this work establishes a fundamental connection between the gradient structure and extra strength in GNT Cu through the mechanistic linkages of plastic strain gradient, heterogeneous dislocation structure, microscale internal stress, and extra back stress. Broadly, this work exemplifies a general approach to unraveling the strengthening mechanisms in heterogeneous nanostructured materials.