Arrival times of compressional (P) and shear (S) waves generated by earthquakes located in the New Hebrides subduction zone and recorded by local and regional arrays of seismographs are used to determine large‐scale one‐ and three‐dimensional elastic wave velocity structures of the subduction zone between 15° and 20°S and from the surface to about 250 km depth. The results obtained from inverting the locally and regionally recorded arrival times individually corroborate each other, and they are inverted jointly in order to improve the resolution of shallow to intermediate depth structures. The results for one‐dimensional structure indicate a gradual increase of velocity with depth until a 9% reversal appears between 60 and 100 km depth. The three‐dimensional structure determined from the joint inversion shows that these low velocities lie within a sizable seismic gap in the descending Benioff zone. Taken with other observations such as the attenuation of high‐frequency shear waves travelling across this gap and the locations of active volcanoes at the surface, we infer that the low‐velocity region represents a thermal anomaly of about 750°C which alters the physical properties of the descending plate in this region. At shallower depths there is evidence of low‐velocity structures included in the descending plate: one beneath north Malekula island and another between Malekula and Efate islands corresponding to the large embayment of the leading edge of the upper plate. The locations of these structures combined with previous investigations of the area lead us to infer that these low velocities are due to the subduction of small‐scale features such as seamounts and accretionary wedges.