The occurrence rate of long-period giant planets around young stars is highly uncertain since it is not only governed by the protoplanetary disc structure and planet formation process, but also reflects dynamical re-structuring processes after planet formation as well as possible capture of planets not formed in-situ. Direct imaging is currently the only feasible method to detect such wide-orbit planets and constrain their occurrence rate. We carry out a large L'-band high-contrast direct imaging survey for giant planets around young stars with protoplanetary or debris discs using the NACO instrument at the ESO Very Large Telescope on Cerro Paranal in Chile. We use very deep angular differential imaging observations with typically >60 deg field rotation, and employ a vector vortex coronagraph where feasible to achieve the best possible point source sensitivity down to an inner working angle of about 100mas. This paper introduces our NACO Imaging Survey for Planets around Young stars ("NACO-ISPY"), its goals and strategy, the target list, and data reduction scheme, and presents preliminary results from the first 2.5 survey years. We achieve a mean 5 sigma L' contrast of 6.4mag at 150mas and a background limit of 16.5mag at >1.5". Our detection probability is >50\% for companions with 8\,M$_{\rm Jup}$\ at semi-major axes 80-200au. It thus compares well to the detection space of other state-of-the-art high-contrast imaging surveys. We have contributed to the characterisation of two new planets originally discovered by VLT/SPHERE, but we have not yet independently discovered new planets around any of our target stars. We report the discovery of close-in low-mass stellar companions around four young stars and show L'-band scattered light images of the discs around eleven stars, six of which have never been imaged at L'-band before.