Half-Heusler (HH) compounds have shown high Figure of merits up to 1.5. The key to these high thermoelectric efficiencies is an intrinsic phase separation, which occurs in multicomponent Half-Heusler compounds and leads to an significantly reduction of the thermal conductivity. For commercial applications, compatible n- and p-type materials are essential and their thermal stability under operating conditions, e.g. for an automotive up to 873 K, needs to be guaranteed. For the first time, the long-term stability of n- and p-type HH materials is proved. We investigated HH materials based on the Ti0.3Zr0.35Hf0.35NiSn-system after 500 cycles (1700 h) from 373 to 873 K. Both compounds exhibit a maximum Seebeck coefficient of S around 210 muV/K and an intrinsic phase separation into two HH phases. The dendritic microstructure is temperature resistant and maintained the low thermal conductivity values (kappa less than 4 W/Km). Our results emphasize that phase-separated HH compounds are suitable low cost materials and can lead to enhanced thermoelectric efficiencies beyond the set benchmark for industrial applications. ; Comment: 10 pages, 4 figures, submitted to Phys. Chem. Chem. Phys