Despite the effectiveness of sodium as a p-type dopant for lead chalcogenides, its solubility is shown to be very limited in these hosts. Here, a high thermoelectric efficiency of ≈2 over a wide temperature range is reported in multiphase quaternary (PbTe)0.65(PbS)0.25(PbSe)0.1 compounds that are doped with sodium at concentrations greater than the solubility limits of the matrix. Although these compounds present room temperature thermoelectric efficiencies similar to sodium doped PbTe, a dramatically enhanced Hall carrier mobility at temperatures above 600 K for heavily doped compounds results in significantly enhanced thermoelectric efficiencies at elevated temperatures. This is achieved through the composition modulation doping mechanism resulting from heterogeneous distribution of the sodium dopant between precipitates and the matrix at elevated temperatures. These results can lead to further advances in designing high performance multiphase thermoelectric materials with intrinsically heterogeneous dopant distributions.