A search for unstable neutral and charged heavy leptons as well as for stable charged heavy leptons has been made at center-of-mass energies √s = 161 GeV and √s = 172 Gev with the L3 detector at LEP. No evidence for their existence was found. We exclude unstable neutral leptons of Dirac (Majorana) type for masses below 78.0 (66.7), 78.0 (66.7) and 72.2 (58.2) GeV, if the heavy neutrino couples to the electron, muon or tau family, respectively. We exclude unstable charged heavy leptons for masses below 81.0 GeV for a wide mass range of the associated neutral heavy lepton. The production of stable charged heavy leptons with a mass less than 84.2 GeV is also excluded. If the unstable charged heavy lepton decays via mixing into a massless neutrino, we exclude masses below 78.7 GeV.