The Complete Calibration of the Colour-Redshift Relation survey (C3R2) is a spectroscopic e ffort involving ESO and Keck facilities designed specifically to empirically calibrate the galaxy colour-redshift relation - P(z jC) to the Euclid depth (iAB = 24 :5) and is intimately linked to the success of upcoming Stage IV dark energy missions based on weak lensing cosmology. The aim is to build a spectroscopic calibration sample that is as representative as possible of the galaxies of the Euclid weak lensing sample. In order to minimise the number of spectroscopic observations necessary to fill the gaps in current knowledge of the P(z jC), self-organising map (SOM) representations of the galaxy colour space have been constructed. Here we present the first results of an ESO@VLT Large Programme approved in the context of C3R2, which makes use of the two VLT optical and near-infrared multi-object spectrographs, FORS2 and KMOS. This data release paper focuses on high-quality spectroscopic redshifts of high-redshift galaxies observed with the KMOS spectrograph in the near-infrared H- and K-bands. A total of 424 highly-reliable redshifts are measured in the 1:3 2 galaxies.