We have collected the most complete multi-wavelength (6.0-6.0E^-18^cm) dataset of very high energy (VHE) gamma-ray emitting (TeV) BL Lacs, which are the most numerous extragalactic VHE sources. Using significant correlations between different bands, we aim to identify the best TeV BL Lac candidates that can be discovered by the current and next generation of imaging air Cherenkovtelescopes. We formed five datasets from lower energy data, i.e. radio, mid-infrared, optical, X-rays, and GeV gamma-ray, and five VHE gamma-ray datasets to perform a correlation study between different bands and to construct the prediction method. The low energy datasets were averaged for individual sources, while the VHE gamma-ray data were divided into subsets according to the flux state of the source. We then looked for significant correlations and determined their best-fit parameters. Using the best-fit parameters we predicted the level of VHE gamma-ray flux for a sample of 182 BL Lacs, which have not been detected at TeV energies. We identified the most promising TeV BL Lac candidates based on the predicted VHE gamma-ray flux for each source. We found 14 significant correlations between radio, mid-infrared, optical, gamma-ray, and VHE gamma-ray bands. The correlation between optical and VHE gamma-ray luminosity is established for the first time. We attribute this to the more complete sample and more accurate handling of host galaxy flux in our work. We found nine BL Lac candidates whose predicted VHE gamma-ray flux is high enough for detection in less than 25 hours with current imaging air Cherenkov telescopes.