Context. Blazars are the most numerous class of High Energy (HE; E about 50 MeV - few 100 GeV) and Very High Energy (VHE; E about 100 GeV - 10 TeV) gamma-ray emitters. As of today, a measured spectroscopic redshift is available for only about 50% of gamma-ray BL Lacs, mainly due to the difficulty of measuring reliable redshifts from their nearly featureless, continuum-dominated optical spectra. The knowledge of the redshift is fundamental for understanding the emission from blazars, for population studies and also for indirect studies of the extragalactic background light and searches for Lorentz invariance violation and axion-like particles using blazars. Aims. This paper is the first of a series of papers which aim to measure the redshift of a sample of blazars likely to be detected with the upcoming Cherenkov Telescope Array (CTA), a ground based gamma-ray observatory. Methods. Monte Carlo simulations were performed to select those hard spectrum gamma-ray blazars detected with the Fermi-LAT telescope still lacking redshift measurements but likely to be detected by CTA in 30 hours of observing time or less. Optical observing campaigns involving deep imaging and spectroscopic observations were organised to efficiently constrain their redshifts. We performed deep medium to high resolution spectroscopy of nineteen blazar optical counterparts using the ESI spectrograph at Keck, the RSS spectrograph at the SALT telescope, and the EFOSC2 spectrograph at the ESO NTT. We searched systematically for spectral features and, when possible, we estimated the contribution of the host galaxy to the total flux. Results. We measured eleven firm spectroscopic redshifts with values ranging from 0.1116 to 0.482. one tentative redshift, three redshift lower limits including one at z > 0.449 and another at z > 0.868. There were four objects found to have featureless spectra.