The mechanical behaviour of directionally solidified NiAl-Mo and NiAl- Mo(Re) eutectic alloys has been examined. The fracture toughness of a NiAl- 9 at.% Mo eutectic alloy is a factor of at least two higher than that of monolithic NiAl. No single dominant toughening mechanism was identified. The toughness enhancement was attributed to a combination of intrinsic toughening of NiAl due to dislocations generated from the interfaces, crack trapping, crack deflection along interfaces and crack bridging. The Mo fibres were solid solution strengthened by Al and Ni partitioned from the NiAl matrix and had low ductility. Extensive interface debonding was noted, particularly when the fibres were either inclined or parallel to the crack plane. The deflection of the crack along the interfaces was analysed in terms of the elastic and plastic properties of the two phases. Alloying with Re was effective in reducing the hardness of Mo fibres in the composite, but also reduced the fibre alignment relative to that of the NiAl-9 at. % Mo alloys. No change in the extent of interface debonding was noted in the Re-alloyed composites. The toughnesses of NiAl-Mo(Re) and NiAl-Mo alloys were compared in the light of the differences in microstructures and effects of Re on ductility of Mo fibres. Solidification processing methods are suggested to produce NiAl-Mo(Re) alloys having completely eutectic microstructures with fibres well aligned along the growth direction to allow direct comparison with the NiAl-9 at. % Mo eutectic alloy.