We investigated the effect of Cd and Hg substitution on the thermoelectric properties of p-type PbTe-x% CdTe and PbTe-x% HgTe (1 <= x <= 5) doped with Na2Te. Both ingot samples and spark plasma sintered (SPS) samples were studied and the properties are compared. We present detailed structural, spectroscopic and transmission electron microscopy (TEM) data, and transport properties of both cast ingot and SPS samples. The SPS processed samples with HgTe as the second phase show better thermoelectric properties than those with CdTe mainly because of more effective phonon scattering. The SPS process gives significantly lower lattice thermal conductivity for the p-type PbTe-HgTe system than the cast ingot. The same effect is not observed in the p-type PbTe-CdTe system. A maximum ZT of similar to 1.64 at similar to 770 K is achieved for the p-type PbTe-2% HgTe-1% Na2Te SPS sample. TEM studies reveal the formation of nanostructures whose number density generally increases with increasing concentrations of CdTe and HgTe as the second phase. Meso-scale grain boundaries along with nanostructured precipitates in the SPS samples play an important role in significantly reducing the lattice thermal conductivity compared to cast ingot in the case of p-type PbTe-HgTe.