ABSTRACT The REX (Radio-Emitting X-ray sources) is a catalogue produced by cross-matching X-ray data from the ROSAT-PSPC archive of pointed observations and radio data from the NRAO VLA Sky Survey, aimed at the selection of blazars. From the REX catalogue, we select a well-defined and statistically complete sample of high-energy peaked BL Lac (HBL). HBL are expected to be the most numerous class of extragalactic TeV-emitting sources. Specifically, we have considered only the REX sources in the currently planned CTA extragalactic survey area satisfying specific criteria and with an optical spectroscopic confirmation. We obtain 46 HBL candidates that we called Te-REX (TeV-emitting REX). We estimate the very high-energy gamma-ray emission, in the TeV domain, using an empirical approach i.e. using specific statistical relations between gamma-rays (at GeV energies) and radio/X-rays properties observed in bright HBL from the literature. We compare the spectral energy distributions (SEDs) with the sensitivities of current and upcoming Cherenkov telescopes and we predict that 14 Te-REX could be detectable with 50 h of observations of CTA and 7 of them also with current Cherenkov facilities in 50 h. By extrapolating these numbers on the total extragalactic sky, we predict that about 800 HBL could be visible in pointed CTA observations and ∼400 with current Cherenkov telescopes in 50 h. Interestingly, our predictions show that a non-negligible fraction (∼30 per cent) of the HBL that will be detectable by CTA is composed of relatively weak objects whose optical nuclear emission is swamped by the host-galaxy light and not (yet) detected by Fermi-LAT.