We investigate the stability of hole polarons at the rutile surface induced by electronegative adsorbates in the intermediate steps of the oxygen evolution reaction through hybrid density functional calculations. Applying the computational hydrogen electrode method, we find that hole polarons reduce the overpotential of the reaction-determining step leading to good agreement with experiment. The stability of the polarons is confirmed at the hydrated surface through a free energy study involving the explicit solvent. The occurrence of surface hole polarons is unrelated to the scaling relationships and offers an additional handle in the search for improved catalysts.