Thermoelectric materials, which can convert waste heat into electricity, have received increasing research interest in recent years. This paper describes the recent progress in thermoelectric nanocomposites based on solution-synthesized nanoheterostructures. We start our discussion with the strategies of improving the power factor of a given material by using nanoheterostructures. Then we discuss the methods of decreasing thermal conductivity. Finally, we highlight a way of decoupling power factor and thermal conductivity, namely, incorporating phase-transition materials into a nanowire heterostructure. We have explored the lead telluride–copper telluride thermoelectric nanowire heterostructure in this work. Future possible ways to improve the figure of merit are discussed at the end of this paper.