Tomographic images of mantle structure beneath the region north and northeast of Australia show a number of anomalously fast regions. These are interpreted using a recent plate tectonic reconstruction in terms of current and former subduction systems. Several strong anomalies are related to current subduction. The inferred slab lengths and positions are consistent with Neogene subduction beneath the New Britain and Halmahera arcs, and at the Tonga and the New Hebrides trenches where there has been rapid rollback of subduction hinges since about 10 Ma. There are several deeper flat-lying anomalies which are not related to present subduction and we interpret them as former subduction zones overridden by Australia since 25 Ma. Beneath the Bird’s Head and Arafura Sea is an anomaly interpreted to be due to north-dipping subduction beneath the Philippines–Halmahera arc between 45 and 25 Ma. A very large anomaly extending from the Papuan peninsula to the New Hebrides, and from the Solomon Islands to the east Australian margin, is interpreted to be the remnant of south-dipping subduction beneath the Melanesian arc between 45 and 25 Ma. This interpretation implies that a flat-lying slab can survive for many tens of millions of years at the bottom of the upper mantle. In the lower mantle there is a huge anomaly beneath the Gulf of Carpentaria and east Papua New Guinea. This is located above the position where the tectonic model interprets a change in polarity of subduction from north-dipping to south-dipping between 45 and 25 Ma. We suggest this deep anomaly may be a slab subducted beneath eastern Australian during the Cretaceous, or subducted north of Australia during the Cenozoic before 45 Ma. The tomography also supports the tectonic interpretation which suggests little Neogene subduction beneath western New Guinea since no slab is imaged south of the New Guinea trench. However, one subduction zone in the tectonic model and many others, that associated with the Trobriand trough east of Papua New Guinea and the Miocene Maramuni arc, is not seen in the tomographic images and may require reconsideration of currently accepted tectonic interpretations.