The microstructure and electrochemical promotion of thin Pd catalyst-electrodes deposited on yttria-stabilized zirconia (YSZ) prepared either by sputter-deposition or wet impregnation has been studied for the complete oxidation of methane using XRD, XPS and steady state catalytic measurements in conjunction to electrochemical studies at temperatures 350-460 degrees C under various CH4 to O-2 ratios. As prepared sputtered catalyst electrodes, which consist mainly of a Pd metal phase are able to electrochemically promote the CH4 oxidation, while impregnated films, which mainly consist of a PdO phase, can be electropromoted only after in situ reduction. On both types of catalyst-electrodes the reaction exhibits electrophobic behavior under all experimental conditions of this study, i.e. the rate increases moderately with anodic polarization. For sputtered samples, negative current application causes a decrease of the catalytic rate which remains lower than the initial open circuit rate after current interruption. This is a new type of permanent electrochemical promotion and a poisoning index, beta, is introduced to quantify the magnitude of this effect. (C) 2012 Elsevier B.V. All rights reserved.