A search for proton decay into three charged leptons has been performed by using 0.37 Mton·years of data collected in Super-Kamiokande. All possible combinations of electrons, muons, and their antiparticles consistent with charge conservation were considered as decay modes. No significant excess of events has been found over the background, and lower limits on the proton lifetime divided by the branching ratio have been obtained. The limits range between 9.2×1033 and 3.4×1034 years at 90% confidence level, improving by more than an order of magnitude upon limits from previous experiments. A first limit has been set for the p→μ-e+e+ mode.