Heterostructures of germanium antimony tellurides with skutterudite-type precipitates are promising thermoelectric materials due to low thermal conductivity and multiple ways of tuning their electronic transport properties. Materials with the nominal composition [CoSb2(GeTe)0.5]x(GeTe)10.5Sb2Te3 (x = 0-2) contain nano- to microscale precipitates of skutterudite-type phases which are homogeneously distributed. Powder X-ray diffraction reveals that phase transitions of the germanium antimony telluride matrix depend on its GeTe content. These are typical for this class of materials; however, the phase transition temperatures are influenced by heterostructuring in a beneficial way, yielding a larger existence range of the intrinsically nanostructured pseudocubic structure of the matrix. Using microfocused synchrotron radiation in combination with crystallite pre-selection by means of electron microscopy, single crystals of the matrix as well as of the precipitates were examined. They show nano-domain twinning of the telluride matrix and a pronounced structure distortion in the precipitates caused by GeTe substitution. Thermoelectric figures of merit of 1.4 ± 0.3 at 450 °C are observed. In certain temperature ranges, heterostructuring involves an improvement of up to 30% compared to the homogeneous material.