Carbon oxidation is a main industrial problem for alumina-graphite refractory base materials used in commercial Submerged Entry Nozzles (SEN) during preheating. Thus, the effects of the plasma spray-PVD coating of the Yttria Stabilized Zirconia (YSZ) powder on the carbon oxidation were investigated. Laboratory preheating trials were performed at non-isothermal heating conditions in a controlled atmosphere. Also, the applied temperature profile for the laboratory trials were defined based on industrial preheating trials. The controlled atmospheres consisted of CO2, O2 and Ar. The (CO2/O2) ratios were kept the same as for a propane combustion flue gas at an Air-Fuel-Ratio (AFR) value equal to 1.5 for heating in an air-fuel mixture and in air. The thicknesses of the decarburized layers were measured and examined using light optic microscopy, FEG-SEM and EDS. The YSZ plasma-PVD coated alumina-graphite refractory base materials, presented the effective resistance to carbon oxidation at different coating thicknesses from 160-480 µm in both combustion flue gas and air atmospheres. For the YSZ plasma coating that contained a thinner coating layer such as 160 µm, the uneven surface of the substrate may be reflected more than it could be reflected for a thicker coating. However, for the YSZ plasma coating with a coating thickness of 290 µm, the uneven surface of the substrate may be reflected much less than it could be reflected for thinner coatings. A 250µm and a 290µm YSZ coating may prevent the decarburization of an alumina-graphite refractory base materials during preheating in air at a maximum heating temperature of 1020°C. Moreover, in an oxidizing atmosphere with an AFR value equal to 1.5 at a maximum temperature of 1020°C and a holding time of 7200 seconds. A 250-290 µm YSZ coating is suggested to be an appropriate coating, as it provides both an even surface and prevention of the decarburization even during heating in air. In addition, the interactions between the YSZ coated alumina-graphite refractory base materials in contact with a cerium alloyed molten stainless steel were surveyed. The YSZ coating provided a total prevention of the alumina reduction by cerium. Therefore, the prevention of the first clogging product formed on the surface of the SEN refractory base materials. Therefore, the YSZ plasma-PVD coating can be recommended for coating of the hot surface of the commercial SENs.