We studied the effect of embedded nanograins on the strength and deformation of nanodomained heterogeneous nickel (Ni) via a novel discrete-crystal plasticity model. Nanodomained structures exhibited higher strength than those of heterogeneous lamella structures and rule of mixtures. Due to the mismatch of strengths between the nanograins and coarse grains, geometrically necessary dislocations (GND) accumulated around nanograins and increased with the strain. In addition, smaller nanograins are more effective to generate GND in both nanodomained and heterogeneous lamella structures. These findings shed light on the role of dislocation mechanisms in the plasticity of heterogeneous nanostructured metals.