The last decade has witnessed nanocomposites becoming a new paradigm in the field of thermoelectric (TE) research. At its core is to prepare high performance TE nanocomposites, both p- and n-type, in a time and energy efficient way. To this end, we in this article summarize our recent effort and results on both p- and n-type Bi2Te3-based nanocomposites prepared by a unique single-element-melt-spinning spark-plasma sintering procedure. The results of transport measurements, scanning and transmission electronic microscopy, and small angle neutron scattering have proved essential in order to establish the correlation between the nanostructures and the TE performance of the materials. Interestingly, we find that in situ formed nanocrystals with coherent boundaries are the key nanostructures responsible for the significantly improved TE performance of p-type Bi2Te3 nanocomposites whereas similar nanostructures turn out to be less effective for n-type Bi2Te3 nanocomposites. We also discuss the alternative strategies to further improve the TE performance of n-type Bi2Te3 materials via nanostructuring processes.