We search for pair production of doubly charged Higgs particles (H±±) followed by decays into electron-tau (eτ) and muon-tau (μτ) pairs using data (350  pb−1) collected from pp collisions at s√=1.96  TeV by the CDF II experiment. We search separately for cases where three or four final-state leptons are detected, and combine results for exclusive decays to left-handed eτ (μτ) pairs. We set an H±± lower mass limit of 114(112)  GeV/c2 at the 95% confidence level.