Thermoelectric heat-to-power generation is an attractive option for robust and environmentally friendly renewable energy production. Historically, the performance of thermoelectric materials has been limited by low efficiencies, related to the thermoelectric figure-of-merit ZT. Nanostructuring thermoelectric materials have shown to enhance ZT primarily via increasing phonon scattering, beneficially reducing lattice thermal conductivity. Conversely, density-of-states (DOS) engineering has also enhanced electronic transport properties. However, successfully joining the two approaches has proved elusive. Herein, we report a thermoelectric materials system whereby we can control both nanostructure formations to effectively reduce thermal conductivity, while concurrently modifying the electronic structure to significantly enhance thermoelectric power factor. We report that the thermoelectric system PbTe-PbS 12% doped with 2% Na produces shape-controlled cubic PbS nanostructures, which help reduce lattice thermal conductivity, while altering the solubility of PbS within the PbTe matrix beneficially modifies the DOS that allow for enhancements in thermoelectric power factor. These concomitant and synergistic effects result in a maximum ZT for 2% Na-doped PbTe-PbS 12% of 1.8 at 800 K.