Micrometer-sized γ−Ni dendrite reinforced nanoeutectic matrix composites have been developed in (Ni0.92Zr0.08)100–xAlx (0 ≤ x ≤ 4) by arc melting. The eutectic matrix is composed of alternate nano-lamellae of intermetallic Ni5Zr and fcc–Ni solid solution phases. All these composites exhibit very high strength, large compressive plasticity ∼25% and strain-hardening up to 1780 MPa. Al dissolves in γ−Ni(Zr) solid solution phase, decreases its hardness/strength, and increases the volume % of γ−Ni dendrite from 20% (x = 0) to 29% (x = 4). Whereas, refinement of the eutectic lamellae thickness from 275 nm (x = 0) to 160 nm (x = 4) increases the matrix hardness and retains the global strength of the composites. The effect of Al addition on the microstructure formation, volume fraction as well as the length scale of the constituent phases, and mechanical properties, have been discussed using an analytical model.