A search for pair-produced doubly charged Higgs bosons has been performed using data samples corresponding to an integrated luminosity of about 614 pb-1 collected with the OPAL detector at LEP at centre-of-mass energies between 189GeV and 209GeV. No evidence for a signal has been observed. A mass limit of 98.5GeV/c2 at the 95% confidence level has been set for the doubly charged Higgs particle in left-right symmetric models. This is the first search for doubly charged Higgs bosons at centre-of-mass energies larger than 91GeV.