The VISTA Magellanic Cloud (VMC; PI: M.-R. L. Cioni) survey is collecting deep K_s_-band time series photometry of the pulsating variable stars hosted by the system formed by the two Magellanic Clouds (MCs) and the bridge connecting them. In this paper, we present the first results for classical Cepheids, from the VMC observations of two fields in the Large Magellanic Cloud (LMC), centred on the South Ecliptic Pole and the 30 Doradus star-forming regions, respectively. The VMC K_s_-band light curves of the Cepheids are well sampled (12 epochs) and of excellent precision (typical errors of ~0.01mag). We were able to measure for the first time the K_s_magnitude of the faintest classical Cepheids in the LMC (K_s_~17.5mag), which are mostly pulsating in the first overtone (FO) mode, and to obtain FO period--luminosity (PL), period-Wesenheit (PW) and period-luminosity-colour (PLC) relations, spanning the full period range from 0.25 to 6d. Since the longest period Cepheid in our data set has a variability period of 23d, we have complemented our sample with literature data for brighter F Cepheids. On this basis, we have built a PL relation in the K_s_ band that, for the first time, includes short-period - hence low-luminosity - pulsators, and spans the full range from 1.6 to 100 d in period.We also provide the first ever empirical PW and PLC relations using the (V-K_s_) colour and time series K_s_photometry. The very small dispersion (~0.07mag) of these relations makes them very well suited to study the three-dimensional geometry of the Magellanic system. The use of 'direct' (parallax- and Baade--Wesselink-based) distance measurements to both Galactic and LMC Cepheids allowed us to calibrate the zero-points of the PL, PW and PLC relations obtained in this paper, and in turn to estimate an absolute distance modulus of (m-M)_0_=18.46+/-0.03mag for the LMC. This result is in agreement with most of the latest literature determinations based on classical Cepheids.