In here, we will show the nanostructured effect on the thermoelectric properties of PbTe alloys. Firstly, the relationship between nano grain size and thermoelectric properties is shown. It is found that thermoelectric figure of merit, zT, strongly depends on the synthesis condition and that its value can be enhanced to ∼2.0 at 773 K by optimizing the size distribution of the nanostructures in the material. Secondly, by varying the quenching time of Na doped PbTe, followed by hot pressing, heterogeneous nanocomposites, a mixture of nanodot nanocomposites and nanograined nanocomposites, have been synthesized. It is found that figures of merit, zT, of those heterogeneous nanocomposites exhibited a zT in 2.0-2.2 at 773 K, which is a 25% increase compared to zT of a homogeneous nanodot nanocomposite. Therefore, the heterogeneous nanostructure should be a better way to enhance the thermoelectric performance of bulk PbTe.