Heterostructures that consist of a germanium antimony telluride matrix and cobalt germanide precipitates can be obtained by straightforward solid-state synthesis including simple annealing and quenching procedures. The microscale precipitates are homogeneously distributed in a matrix with pronounced "herringbone-like" nanostructure associated with very low thermal conductivities. In comparison to the corresponding pure tellurides, the figure of merit (ZT) values of heterostructured materials are remarkably higher This is mostly due to an increase of the Seebeck coefficient with only little impact on the electrical conductivity. In addition, the phononic part of the thermal conductivity is significantly reduced in some of the materials. As a result, ZT values of ca. 1.9 at 450 degrees C are achieved. Temperature-dependent changes of the thermoelectric properties are well-understood and correlate with complex phase transitions of the telluride matrix. However, the high ZT values are retained in multiple measurement cycles.