Nanostructuration and nanocomposites have shown great potential for improving the efficiency of thermoelectric materials. By using only physical vapor deposition techniques, nanocomposites composed of Fe nanoparticles embedded into a CrN matrix were produced. By using a combinatorial process of high-power impulse magnetron sputtering and a so-called nanoparticle gun, multilayer nanocomposite coatings were deposited. The combinatorial technique allowed the formation of nanocomposites in which the Fe nanoparticles remained intact without reaction with the matrix. The measured thermoelectric properties of the coatings revealed an increase in the Seebeck coefficient, with a decrease in the electrical conductivity after insertion of Fe nanoparticle. This change of behavior has been correlated to the variation of charge carrier concentration and electron mobility. This study shows the potential of the synthesis process used for creating nanocomposites, and of the strategy used for improving the thermoelectric properties of coatings.