During 1997 July/August, we conducted the first deep survey of the sky at sub-mm wavelengths using the new SCUBA sub-mm camera (Smail, Ivison & Blain 1997). Our sub-mm maps cover a total area of 20 arcmin^2 to 1-sigma noise levels less than 13 and 2 mJy/beam at 450 and 850um. We have concentrated on lensing clusters to exploit the amplification of background sources by the cluster, improving the sensitivity by a factor of 1.3-2.0 as compared with a blank-field survey. A cumulative source surface density of 2400 +/- 1000 per square degree is found to a 50% completeness limit of 4 mJy at 850um. The sub-mm spectral properties of these sources indicate that the majority lie at high redshift, z >> 1. Without correcting for lens amplification, our observations place a firm upper limit on the blank-field counts at this depth. This surface density is 3 orders of magnitude greater than the expectation of a non-evolving model using the local IRAS 60-um luminosity function. The observed source counts thus require a substantial increase in the number density of strongly star-forming galaxies in the high-redshift Universe. The magnitude of this increase indicates that optical surveys of the star-formation properties of the distant Universe have missed substantial numbers of obscured star-forming galaxies. This provides strong constraints on the formation of normal galaxies. Clearly, the consequences of these observations are extremely far-reaching and it is vital that we obtain follow-up multi-frequency observations of the detected sources to determine where they fit in to our picture of galaxy evolution. Already, we have obtained extremely deep B-, V-, R-, I- and K-band images and deep X-, C- and L-band radio maps. These show that the detected sources have extremely red spectral energy distributions and do not have active nuclei. Here, we request an allocation of 20ks to determine their rest-frame mid-IR spectral energy distributions, vital for constraining the properties of these galaxies.