Ionization of hydrochloric acid (HCl) on stratospheric ice particles is believed to be a key step in the depletion of stratospheric ozone. Ab initio calculations based on a model HCl-water cluster show that HCl ionization on ice surfaces is a barrierless process. Since this mechanism is rapid and produces chloride anions that are exposed to ambient stratospheric chlorine reservoir molecules, it is likely to be important for stratospheric chemistry. It complements a previously suggested mechanism where HCl forms part of the ice lattice before ionizing. The mechanism proposed here is also consistent with experimentally observed ionization of HCl on ice at low temperatures and under vacuum, where the HCl is not expected to be encapsulated in the ice lattice.