A long-standing technological challenge to the widespread application of thermoelectric generators is obtaining high-performance thermoelectric materials from abundant elements. Intensive study on PbTe alloys has resulted in a high figure of merit for the single-phase ternary PbTe-PbSe system through band structure engineering, and the low thermal conductivity achieved due to nanostructuring leads to high thermoelectric performance for ternary PbTe-PbS compounds. Recently, the single-phase p-type quaternary PbTe-PbSe-PbS alloys have been shown to provide thermoelectric performance superior to the binary and ternary lead chalcogenides. This occurs via tuning of the band structure and from an extraordinary low thermal conductivity resulting from high-contrast atomic mass solute atoms. Here, we present the thermoelectric efficiency of nanostructured p-type quaternary PbTe-PbSe-PbS composites and compare the results with corresponding single-phase quaternary lead chalcogenide alloys. We demonstrate that the very low lattice thermal conductivity achieved is attributed to phonon scattering at high-contrast atomic mass solute atoms rather than from the contribution of secondary phases. This results in a thermoelectric efficiency of ∼1.4 over a wide temperature range (650-850 K) in a p-type quaternary (PbTe)0.65(PbSe)0.1(PbS)0.25 composite that is lower than that of single-phase (PbTe)0.85(PbSe)0.1(PbS)0.05 alloy without secondary phases.