A search for pair production of new heavy leptons has been performed assuming different scenarios for the mixing of the new particles with Standard Model leptons. No candidate events were found in a data sample corresponding to an integrated luminosity of 5.6 pb−1 collected by the ALEPH detector at centre-of-mass energies of 130 and 136 GeV. New limits on production cross-sections and on masses of sequential leptons were obtained which significantly extend the mass regions excluded at LEP1. For instance, charged heavy leptons with masses below 63.5 GeV/c2 are excluded at 95% C.L. for mass differences to the associated neutral lepton of more than 7 GeV/c2.