We present a molecular line scan in the Hubble Deep Field North (HDF-N) that covers the entire 3mm window (79-115 GHz) using the IRAM Plateau de Bure Interferometer. Our CO redshift coverage spans z<0.45, 1<z<1.9 and all z>2. We reach a CO detection limit that is deep enough to detect essentially all z>1 CO lines reported in the literature so far. We have developed and applied different line searching algorithms, resulting in the discovery of 17 line candidates. We estimate that the rate of false positive line detections is ~2/17. We identify optical/NIR counterparts from the deep ancillary database of the HDF-N for seven of these candidates and investigate their available SEDs. Two secure CO detections in our scan are identified with star-forming galaxies at z=1.784 and at z=2.047. These galaxies have colors consistent with the `BzK color selection and they show relatively bright CO emission compared with galaxies of similar dust continuum luminosity. We also detect two spectral lines in the submillimeter galaxy HDF850.1 at z=5.183. We consider an additional 9 line candidates as high quality. Our observations also provide a deep 3mm continuum map (1-sigma noise level = 8.6 $mu$Jy/beam). Via a stacking approach, we find that optical/MIR bright galaxies contribute only to <50% of the SFR density at 1<z<3, unless high dust temperatures are invoked. The present study represents a first, fundamental step towards an unbiased census of molecular gas in `normal galaxies at high-z, a crucial goal of extragalactic astronomy in the ALMA era.