We report on the detection of very high energy (VHE; E > 100 GeV) gamma-ray emission from the BL Lac objects KUV 00311-1938 and PKS 1440-389 with the High Energy Stereoscopic System (H.E.S.S.). H.E.S.S. observations were accompanied or preceded by multiwavelength observations with Fermi/LAT, XRT and UVOT onboard the Swift satellite, and ATOM. Based on an extrapolation of the Fermi/LAT spectrum towards the VHE gamma-ray regime, we deduce a 95 per cent confidence level upper limit on the unknown redshift of KUV 00311-1938 of z < 0.98 and of PKS 1440-389 of z < 0.53. When combined with previous spectroscopy results, the redshift of KUV 00311-1938 is constrained to 0.51 <= z < 0.98 and of PKS 1440-389 to 0.14 (sic) z < 0.53.