Recent improvements in the performance of thermoelectric materials have resulted from adding nano-structures in order to scatter heat carrying phonons. While this approach effectively reduces the lattice thermal conductivity, it is often accompanied by large drops in the electrical conductivity caused by mobility reductions. In this work we show that bulk forms of Half-Heusler (HH) alloys can be combined with nano-scale Full-Heusler (FH) inclusions to simultaneously improve the power factor and reduce thermal conductivity. HH structures are of the form MNiSn and MCoSb (M= Ti, Zr, or Hf) and the FH counterparts are created by filling the vacancies on the Ni or Co planes respectively, resulting in MNi2Sn and MCo2Sb. Previous experimental results have shown the FH nano-inclusions being coherently integrated into the matrix HH material resulting in enhanced ZT which has been attributed to an energy filtering mechanism that occurs at the HH-FH semi-coherent boundaries as well as moderate reductions in thermal conductivity by nano-inclusion phonon scattering. Ab Initio calculations, in combination with a cluster expansion, are used to test the stability of FH structures in the HH matrix and create a thermodynamic pseudo-binary phase diagram for MNiSn-MNi2Sn compositions. In addition, electronic structure and lattice dynamics are investigated in order to elucidate possibilities for future approaches to enhance ZT. This research is supported by the Department of Energy, Office of Basic Energy Sciences under Award # DE-SC-0008574.