The procedure for preparing a structured composite system Ce0.75Zr0.25O2/θ-Al2O3/FeCrAl, which is used as a support for complete oxidation catalysts and catalysts for the conversion of liquid and gaseous hydrocarbons into synthesis gas, has been improved. The method for the synthesis of Ce0.75Zr0.25O2 powder has been optimized to facilitate its depositing on a FeCrAl mesh pre-coated by protective θ-Al2O3 layer. It has been shown by X-ray diffraction that the model powder sample and the cerium-zirconium mixed oxide coating on the alumina-precoated FeCrAl mesh have the same phase compositions. The protective layer of θ-Al2O3 on FeCrAl mesh possesses excellent adhesion properties that ensures high mechanical strength of the Ce0.75Zr0.25O2 coating under repeated heating–cooling cycles. The use of metal substrate as a component of the composite support provides high thermal conductivity, and thus reduces the formation of local hot spots under conditions of highly exothermic catalytic processes.