Lead chalcogenides are dominant thermoelectric materials in the medium-temperature range, owing to their highly favorable electronic band structures and low thermal conductivities achievable. An important system is the PbTe-PbS pseudo-binary and its low thermal conductivity originates largely from the coexistence of both alloying and nanostructuring through phase-separation. To better understand the competition between alloying and phase separation, and its pronounced effects on the thermoelectric performance in PbTe-PbS, we systematically studied, via transmission electron microscopy (TEM) observations and theoretical calculations, samples of Spark Plasma Sintered (SPSed) 3 at% Na-doped (PbTe)1-x(PbS)x with x=10%, 15%, 20%, 25%, 30% and 35%. The highest figure of merit, viz., ZT~ 2.3 was obtained at 923 K, when the PbS phase-fraction, x, was 20%, corresponding to the lowest lattice thermal conductivity of the series. The consistently lower lattice thermal conductivities in the SPSed samples as compared with the corresponding ingots, originating from the mesostructured nature of the former, contributes significantly to the superior ZT. We also studied the onset of carrier concentration modulation ~600 K, which leads to the observed saturation of electrical transport properties due to the diffusion and re-dissolution of excessive Na into the PbTe-PbS matrix. This carrier concentration modulation, is equally crucial to achieve the very high power factors (up to 26.5 µW/cmK2 at 623 K) and the outstanding thermoelectric performances in SPSed PbTe-PbS binaries.