Two-dimensional hydrodynamical simulations of the deleptonization of a newly formed neutron star were performed. Driven by negative lepton fraction and entropy gradients, convection starts near the neutrinosphere about 20-30 ms after core bounce, but moves deeper into the protoneutron star, and after about one second the whole protoneutron star is convective. The deleptonization of the star proceeds much faster than in the corresponding spherically symmetrical model because the lepton flux and the neutrino luminosities increase by up to a factor of two. The convection below the neutrinosphere raises the neutrinospheric temperatures and mean energies of the emitted neutrinos by 10-20%. This can have important implications for the supernova explosion mechanism and changes the detectable neutrino signal from the Kelvin-Helmholtz cooling of the protoneutron star. In particular, the enhanced electron neutrino flux relative to the electron antineutrino flux during the early post-bounce evolution might solve the overproduction problem of certain elements in the neutrino-heated ejecta in models of type-II supernova explosions.