We report redshift measurements for 12 BL Lacertae objects from a program aimed at obtaining high signal-to-noise ratio (up to ~500) optical spectroscopy of a mixed sample of objects. The new observations, gathered with the 8 m ESO Very Large Telescope, allowed us to detect weak spectral features down to a line equivalent width as small as ~1 Å. The new redshifts fall in the 0.2-1.3 interval. For nine objects we observe emission lines from the active nucleus. In the remaining three cases absorption lines from the host galaxy are found. For two objects we also detect absorption lines from intervening systems.