Since about 2002 the current-generation imaging air Cherenkov telescopes have discovered more than 50 new VHE γ-ray sources. More importantly, new extragalactic source classe have been discovered: radio galaxies, low-peaked BL Lac (LBL) objects, and quasars. BL Lacertae was the first LBL object that has been detected at VHE. With the MAGIC telescope we observed BL Lacertae for 22.2 hr during 2005 August to December and for 26 hr during 2006 July to September. A very high energy (VHE) γ-ray signal was discovered with a 5.1-σ excess in the 2005 data. Above 200 GeV, an integral flux of (0.6+/-0.2)×10-11 cm-2 s-1 was measured. The differential spectrum between 150 and 900 GeV is rather steep with a spectral photon index of -3.6+/-0.5. The light curve shows no significant variability during the observations in 2005. For the first time a clear detection of VHE γ-ray emission from an LBL object was obtained with a signal below previous upper limits. The 2006 data show no significant excess. We also discuss a possible correlation with the optical emission.