© 2019 Elsevier B.V. The southeast (SE)Asia - Australia collision zone is one of the most tectonically active and seismogenic regions in the world. Here, we present new 3-D P- and S-wave velocity models of the crust and upper mantle by applying regional earthquake travel-time tomography to global catalogue data. We first re-locate earthquakes provided by the standard ISC-Reviewed and ISC-EHB catalogues using a non-linear oct-tree scheme. A machine learning algorithm that clusters earthquakes depending on their spatiotemporal density was then applied to significantly improve the consistency of travel-time picks. We used the Fast Marching Tomography software package to retrieve 3-D velocity and interface structures from starting 1-D velocity and Moho models. Synthetic resolution and sensitivity tests demonstrate that the final models are robust, with P-wave speed variations (~130 km horizontal resolution)generally recovered more robustly than S-wave speed variations (~220 km horizontal resolution). The retrieved crust and mantle anomalies offer a new perspective on the broad-scale tectonic setting and underlying mantle architecture of SE Asia. While we observe clear evidence of subducted slabs as high velocity anomalies penetrating into the mantle along the Sunda arc, Banda arc and Halmahera arc, we also see evidence for slab gaps or holes in the vicinity of east Java. In the Banda arc, we image the slab as a single curved subduction zone. Furthermore, a high-velocity region in the mantle lithosphere connects northern Australia with Timor and West Papua. The S-wave model shows broad-scale features similar to those of the P-wave model, with mantle earthquakes generally distributed within high-velocity slabs. The high velocity mantle connection between northern Australia and the eastern margin of the Sunda arc is also present in the S-wave model. While the S-wave model has a lower resolution than the P-wave model due to the availability of fewer paths, it nonetheless provides new and complementary insights into the structure of the upper mantle beneath southeast Asia.