Large reductions in the thermal conductivity of thermoelectrics using nanostructures have been widely demonstrated. Some enhancements in the thermopower through nanostructuring have also been reported. However, these improvements are generally offset by large drops in the electrical conductivity due to a drastic reduction in the mobility. Here, we show that large enhancements in the thermopower and electrical conductivity of half-Heusler (HH) phases can be achieved simultaneously at high temperatures through coherent insertion of nanometer scale full-Heusler (FH) inclusions within the matrix. The enhancements in the thermopower of the HH/FH nanocomposites arise from drastic reductions in the "effective" carrier concentration around 300 K. Surprisingly, the mobility increases drastically, which compensates for the decrease in the carrier concentration and minimizes the drop in the electrical conductivity. Interestingly, the carrier concentration in HH/FH nanocomposites increases rapidly with temperature, matching that of the HH matrix at high temperatures, whereas the temperature dependence of the mobility significantly deviates from the typical T(-alpha) law and slowly decreases (linearly) with rising temperature. This remarkable interplay between the temperature dependence of the carrier concentration and mobility in the nanocomposites results in large increases in the power factor at 775 K. In addition, the embedded FH nanostructures also induce moderate reductions in the thermal conductivity leading to drastic increases in the ZT of HH(1 - x)/FH(x) nanocomposites at 775 K By combining transmission electron microscopy and charge transport data, we propose a possible charge carrier scattering mechanism at the HH/FH interfaces leading to the observed anomalous electronic transport in the synthesized HH(1 - x)/FH(x) nanocomposites.