We report results of a spectroscopic campaign carried out at the 10 m Gran Telescopio Canarias for a sample of 22 BL Lac objects detected (or candidates) at TeV energies, aiming to determine or constrain their redshift. This is of fundamental importance for the interpretation of their emission models and for population studies and is also mandatory for studying the interaction of high-energy photons with the extragalactic background light using TeV sources. Optical spectra with high signal-to-noise ratios in the range 4250–10000 Å were obtained to search for faint emission or absorption lines from both the host galaxy and the nucleus. We determine a new redshift for PKS 1424+240 (z = 0.604) and a tentative one for 1ES 0033+595 (z = 0.467). We are able to set new spectroscopic redshift lower limits for three other sources on the basis of Mg ii and Ca ii intervening absorption features: BZB J1243+3627 (z > 0.483), BZB J1540+8155 (z > 0.672), and BZB 0J2323+4210 (z > 0.267). We confirm previous redshift estimates for four blazars: S3 0218+357 (z = 0.944), 1ES 1215+303 (z = 0.129), W Comae (z = 0.102), and MS 1221.8+2452 (z = 0.218). For the remaining targets, in seven cases (S2 0109+22, 3C 66A, VER J0521+211, S4 0954+65, BZB J1120+4214, S3 1227+25, BZB J2323+4210), we do not validate the proposed redshift. Finally, for all sources of still-unknown redshift, we set a lower limit based on the minimum equivalent width of absorption features expected from the host galaxy.