We report our initial discovery of 73 new planetary nebulae (PNe) in the Large Magellanic Cloud (LMC) following confirmatory 2dF spectroscopy on the Anglo-Australian Telescope. Preliminary candidate sources come from a 10 per cent sub-area of our new deep, high-resolution Hα map of the central 25 deg2 of the LMC obtained with the UK Schmidt Telescope. The depth of the high-resolution map was extended to Requiv ∼ 22 for Hα (4.5 × 10-17 erg cm-2 s-1 Å-1) by a process of multi-exposure median co-addition of a dozen 2-h Hα exposures. The resulting map is at least 1-mag deeper than the best wide-field narrow-band LMC images currently available. This depth, combined with our selection technique, has also led to the discovery of extended asymptotic giant branch (AGB) haloes around many new and previously known LMC PNe for the first time. Once complete, our new survey is expected to triple the LMC PN population and have significant implications for the LMC PN luminosity function, kinematics, abundance gradients, chemical evolution and, via study of the AGB haloes, the initial to final mass relation for low- to intermediate-mass stars.