NiAl base eutectic alloy is an attractive material and promising to use in high temperature environment. However, the inadequate high temperature strength limits its application. In order to improve its strength, Zr was added in the Ti and Hf doped NiAl/Cr(Mo) base eutectic alloys and the effect of Zr addition on microstructure and mechanical properties of the eutectic alloy was investigated in this work. The results show that small addition of Zr can refine the NiAl/Cr(Mo) lamella inside the eutectic cell and optimize NiAl and Cr(Mo) phase morphology in the intercellular zone. Moreover, the Zr addition promotes the precipitation of bulk Heusler phase along eutectic cell boundary. With the increase of Zr addition, the eutectic cell of the alloys becomes fine, but the NiAl and Cr(Mo) phases in the intercellular zone become coarse and the Heusler phases exhibits semi-continuously distribution along the eutectic cell boundary. When the Zr content increases to 1% (atomic fraction), the NiAl and Cr(Mo) phases in eutectic cell and intercellular zone are all coarsened obviously. Additionally, coarse Cr-rich phases precipitate in the intercellular zone and Heusler phase forms the continuous network along eutectic cell boundary. The addition of Zr promotes the precipitation of coarse b-NiAl and a-Cr phase in Cr(Mo) phase and NiAl phases, respectively. Moreover, the segregation of Heusler phase forming elements along the precipitate interface leads to the formation of a large number of interfacial dislocations. In addition, the addition of Zr results in the precipitation of fine Heusler particles in NiAl phase. It is shown that appropriate addition of Zr can improve the compression strength of Ni-33Al-28Cr-5.5Mo-1.0Ti-0.3Hf eutectic alloys significantly at room temperature and high temperature without reducing its compression plasticity, but more addition of Zr reduces the compressive plastic of the alloy inevitably.