A search for lepton-flavor-violating interactions ep → μX and ep → τX has been performed with the ZEUS detector using the entire HERA I data sample, corresponding to an integrated luminosity of 130 pb-1. The data were taken at center-of-mass energies, √s, of 300 and 318 GeV. No evidence of lepton-flavor violation was found, and constraints were derived on leptoquarks (LQs) that could mediate such interactions. For LQ masses below √s, limits were set on λeq1 √β ℓq, where λeq1 is the coupling of the LQ to an electron and a first-generation quark q1, and βℓq is the branching ratio of the LQ to the final-state lepton ℓ (μ or τ) and a quark q. For LQ masses much larger than √s, limits were set on the four-fermion interaction term λeqαλ ℓqβ/MLQ2 for LQs that couple to an electron and a quark qalpha and to a lepton ℓ and a quark q beta, where α and β are quark generation indices. Some of the limits are also applicable to lepton-flavor-violating processes mediated by squarks in R-Parity-violating supersymmetric models. In some cases, especially when a higher-generation quark is involved and for the process ep → τX, the ZEUS limits are the most stringent to date. © Springer-Verlag.