A novel approach for optimization of the thermoelectric properties of p-type Heusler compounds with a C1b structure was investigated. A successful recipe for achieving intrinsic phase separation in the n-type material based on the TiNiSn system is isoelectronic partial substitution of Ti with its heavier homologues Zr and Hf. We applied this concept to the p-type system MCoSb0.8Sn0.2 by a systematic investigation of samples with different compositions at the Ti position (M = Ti, Zr, Hf, Ti0.5Zr0.5, Zr0.5Hf0.5, and Ti0.5Hf0.5). We thus achieved an approximately 40% reduction of the thermal conductivity and a maximum figure of merit ZT of 0.9 at 700 °C. This is a 80% improvement in peak ZT from 0.5 to 0.9 at 700 °C compared to the best published value of an ingot p-type half-Heusler compound. Thus far, comparable good thermoelectric p-type materials of this structure type have only been realized by a nanostructuring process via ball milling of premelted ingot samples followed by a rapid consolidation method, like hot pressing. The herein-presented simple arc-melting fabrication method reduces the fabrication time as compared to this multi-step nanostructuring process. The high mechanical stability of the Heusler compounds is favorable for the construction of thermoelectric modules. The Vickers hardness values are close to those of the n-type material, leading to good co-processability of both materials.