An apparatus in the form of an air preheater for preheating air for combustion for a combustion process by acting upon the air with hot, NO.sub.x -containing flue gases from the same or an independent combustion process. At the same time, the NO.sub.x contained in the flue gases is reduced. A regenerative or recuperative type air preheater is used, with those surfaces of the heat exchange elements which are exposed to the flue gas being provided with a coating which acts as a catalyst for the NO.sub.x reduction. The heat exchange elements are coated only in a region which has a flue gas temperature greater than the condensation temperature of the reaction products of the materials contained in the flue gas and of the added reducing agent. The catalyst coating is provided on individual heat exchange elements which are successively disposed in the direction of flow of the flue gas in such a way that the respective coatings are optimally adapted to the reaction conditions for the flue gas temperature which exists in that region.