Half-Heuslers would be important thermoelectric materials due to their high temperature stability and abundance if their dimensionless thermoelectric figure of merit (ZT) could be made high enough. The highest peak ZT of a p-type half-Heusler has been so far reported about 0.5 due to the high thermal conductivity. Through a nanocomposite approach using ball milling and hot pressing, we have achieved a peak ZT of 0.8 at 700 °C, which is about 60% higher than the best reported 0.5 and might be good enough for consideration for waste heat recovery in car exhaust systems. The improvement comes from a simultaneous increase in Seebeck coefficient and a significant decrease in thermal conductivity due to nanostructures. The samples were made by first forming alloyed ingots using arc melting and then creating nanopowders by ball milling the ingots and finally obtaining dense bulk by hot pressing. Further improvement in ZT is expected when average grain sizes are made smaller than 100 nm.