The microstructure evolution and room temperature fracture toughness of NiAl–Cr(Mo)–(Hf,Dy)–4Fe alloy during heat treatment have been investigated. After heat treatment (1250°C), the NiAl and Cr(Mo) phases become coarse, and a local dissolution occurs in Cr(Mo) lamellae. Simultaneously, fine Hf solid solution appears at the NiAl/Cr(Mo) phase interface. Moreover, the addition of Fe can improve the fracture toughness of NiAl–Cr(Mo)–(Hf,Dy) alloy, and heat treatment can enhance fracture toughness further. The relevant toughness mechanism is also discussed.