The easternmost Coral Sea region is an underexplored area at the northeasternmost corner of the Australian plate. Situated between the Mellish Rise, southern Solomon Islands, northern Vanuatu and New Caledonia, it represents one of the most dynamic and tectonically complex submarine regions of the world. Interactions between the Pacific and Australian plate boundaries have resulted in an intricate assemblage of deep oceanic basins and ridges, continental fragments and volcanic products; yet there is currently no clear conceptual framework to describe their formation. Due to the paucity of geological and geophysical data from the area to constrain plate tectonic models, a novel approach has been developed whereby the history of subduction based on a plate kinematic model is mapped to present-day seismic tomography models. A plate kinematic model, which includes a self-consistent mosaic of evolving plate boundaries through time is used to compute plate velocity fields and palaeooceanic age grids for each plate in 1 million year intervals. Forward geodynamic models, with imposed surface plate velocity constraints are computed using the 3D spherical finite element convection code CitcomS. A comparison between the present-day mantle temperature field predicted by these geodynamic models with seismic tomography suggests that the kinematic model for the subduction history in the eastern Coral Sea works well for the latest Cenozoic but fails to predict seismically fast material in the lower mantle (indicative of cold, subducted material) imaged in seismic tomography models. This implies that the location and nature of the plate boundaries in the eastern Coral Sea used in these models requires further refinement. A quantified tectonic framework and subduction history of the region will assist in assessing hydrocarbon and mineral resource potential of northeastern Australia and Australia’s Pacific island neighbours, the eastward extent of Australian continental lithosphere and will help place further constrains on the subsidence and uplift history of Australia’s eastern sedimentary basins and carbonate-capped plateaus.