The region of northern Borneo in South East Asia sits within a post-subduction setting formed by the recent termination of two sequential but opposed subduction systems. In this study we use seismic data from a recent temporary array deployment to image the crustal velocity structure beneath northern Borneo using a two-stage Bayesian trans-dimensional tomography scheme, in which period dependent phase velocity maps are first generated, and then used to build a 3-D shear wave model through a series of 1-D inversions. In the second stage, we also apply an Artificial Neural Network to solve the 1D inverse problem, which results in a smoother 3-D model compared to the TransD approach without sacrificing data fit. Our shear wave velocity model reveals a complex crustal structure. Under the Crocker Range, a heterogeneous velocity structure likely represents remnants of early Miocene subduction, including underthrust continental crust from subsequent continent-continent collision. In the east we observe high velocities that are interpreted to be igneous rocks in the crust generated by melting due to mid Miocene Celebes Sea subduction and later decompression melting as well as a low velocity zone that could represent underthrust sediment or duplexes from Celebes Sea subduction. A low velocity zone in the lower crust is present in a region of apparent crustal thinning. Our preferred explanation for this anomaly is remnant thermal upwelling within a failed rift that represents the on-shore continuation of the extension of the Sulu Sea, most likely caused by rollback of the Celebes Sea slab.