In this paper, we propose a heterogeneous material for bulk thermoelectrics. By varying the quenching time of Na doped PbTe, followed by hot pressing, we synthesized heterogeneous nanocomposites, a mixture of nanodot nanocomposites and nanograined nanocomposites. It is well-known that by putting excess amounts of Na (i.e., exceeding the solubility limit) into PbTe, nanodots with sizes as small as a few nanometers can be formed. Nanograined regions with an average grain size of ca. 10 nm are observed only in materials synthesized with an extremely low quenching rate, which was achieved by using a quenching media of iced salt water and cold water. Dimensionless thermoelectric figures of merit, zT, of those heterogeneous nanocomposites exhibited a zT around 2.0 at 773 K, which is a 25% increase compared to zT of a homogeneous nanodot nanocomposite with the largest quenching time in our experiment, i.e. furnace cooled. The power factor increase is 5%, and the thermal conductivity reduction is 15%; thus, zT increase mainly comes from the thermal conductivity reduction.