Systematic study was conducted on the microstructures and mechanical properties of nickel samples with two distinct types of heterostructures. The first is featured with coarse-grained lamellae embedded in a matrix consisting of a very high density of dislocation structures. The second is featured with coarse-grained zones embedded in the ultrafine-grained matrix. The second type of heterostructures exhibits better strength and ductility, although it has a smaller average grain size than the first type. The zone boundaries in the second type of heterostructures are less prone to cracking than those in the first type. Intersecting micro-shear-bands formed net-like patterns in the second type of heterostructures during tensile deformation. This is the first ever observation of structural micro-shear-bands in a heterostructured material. It supports the claim that heterostructure promotes the formation of dispersive shear bands. In contrast, a macroscopic shear band formed and caused early failure of the sample with the first type of heterostructures. Our results indicate that well-developed ultrafine/nano grained matrix in heterostructured materials are necessary for preventing crack formation and shear band localization. This should be considered as a key factor for optimizing the mechanical properties of heterostructured materials.