We report a first-principles theoretical investigation of electrochemical promotion induced by controlled variation in catalyst-electrode potential of metals interfaced with solid electrolytes. Cluster models of oxygen adsorbed on Cu and Pt metal surfaces with coadsorbed positive and negative ions have been considered. The presence of the ions has been simulated also by using point charges and uniform electric fields. We have analyzed the dependence of the metal work function and of the oxygen adsorption energy on the magnitude of the point charges or of the external electric fields. The theoretical results are compared with temperature-programmed desorption, TPD, and potentiometric work function measurements for oxygen on Pt films supported on ZrO2, an O2- conductor. The theoretical calculations show the same linear dependence of the O bond strength on the metal work function observed experimentally. This linear relationship is found also at the first-order perturbation theory level by taking into account only the purely electrostatic interaction between the field induced by the ions and the polar metal-oxygen bond. This suggests that the change in oxygen desorption energy is largely due to electrostatic effects. In addition to providing a direct explanation for the effect of electrochemical promotion, the present results may also provide a sound theoretical basis for the study and understanding of the role of promoters in heterogeneous catalysis.