We present the results of a new, ultra-deep, near-infrared imaging survey executed with the Hawk-I imager at the ESO VLT, of which we make all the data (images and catalog) public. This survey, named HUGS (Hawk-I UDS and GOODS Survey), provides deep, high-quality imaging in the K and Y bands over the portions of the UKIDSS UDS and GOODS-South fields covered by the CANDELS HST WFC3/IR survey. In this paper we describe the survey strategy, the observational campaign, the data reduction process, and the data quality. We show that, thanks to exquisite image quality and extremely long exposure times, HUGS delivers the deepest K-band images ever collected over areas of cosmological interest, and in general ideally complements the CANDELS data set in terms of image quality and depth. In the GOODS-S field, the K-band observations cover the whole CANDELS area with a complex geometry made of 6 different, partly overlapping pointings, in order to best match the deep and wide areas of CANDELS imaging. In the deepest region (which includes most of the Hubble Ultra Deep Field) exposure times exceed 80 hours of integration, yielding a 1-o magnitude limit per square arcsec of ' 28:0 AB mag. The seeing is exceptional and homogeneous across the various pointings,confined to the range 0:38 􀀀 0:43 arcsec. In the UDS field the survey is about one magnitude shallower (to match the correspondingly shallower depth of the CANDELS images) but includes also Y-band band imaging (which, in the UDS, was not provided by the CANDELS WFC3/IR imaging). In the K-band, with an average exposure time of 13 hours, and seeing in the range 0:37-0:43 arcsec, the 1-o limit per square arcsec in the UDS imaging is ' 27:3AB mag. In the Y-band, with an average exposure time ' 8 hours, and seeing in the range 0:45- 0:5 arcsec, the imaging yields a 1-o limit per square arcsec of ' 28:3AB mag. We show that the HUGS observations are well matched to the depth of the CANDELS WFC3/IR data, since the majority of even the faintest galaxies detected in the CANDELS H-band images are also detected in HUGS. Finally we present the K-band galaxy number counts produced by combining the HUGS data from the two fields. We show that the slope of the number counts depends sensitively on the assumed distribution of galaxy sizes, with potential impact on the estimated extra-galactic background light.