We report on the discovery of very high energy (VHE) γ-ray emission from the BL Lacertae object 1ES 1011+496. The observation was triggered by an optical outburst in 2007 March and the source was observed with the MAGIC telescope from 2007 March to May. Observing for 18.7 hr, we find an excess of 6.2 σ with an integrated flux above 200 GeV of (1.58 ± 0.32) × 10-11 photons cm-2 s-1. The VHE γ-ray flux is >40% higher than in 2006 March-April (reported elsewhere), indicating that the VHE emission state may be related to the optical emission state. We have also determined the redshift of 1ES 1011+496 based on an optical spectrum that reveals the absorption lines of the host galaxy. The redshift of z = 0.212 makes 1ES 1011+496 the most distant source observed to emit VHE γ-rays to date. © 2007. The American Astronomical Society. All rights reserved.