Heterostructured materials have been reported to possess superior combinations of strength and ductility, which is attributed to hetero-deformation induced (HDI) strengthening and work hardening. However, the influence of heterostructural parameters on the evolution of HDI stress and mechanical behavior during tensile deformation is not well understood. In this paper, heterostructured brass (Cu–30%Zn) was fabricated by cold rolling and partial annealing, to produce heterostructures with different heterostructural parameters, including domain volume fraction, domain thickness/spacing and domain misorientation. It was found that HDI hardening was dominant when the tensile strain was less than ∼4.5%, while conventional dislocation hardening became more effective at higher strain levels. Quick accumulation of geometrically necessary dislocations was found in the domain boundary regions, leading to high HDI stress. Higher domain misorientation was found more effective in developing HDI hardening. These findings elucidate the effect of heterostructure on strength and ductility, which can help with the design of heterostructured materials for superior mechanical properties.