Understanding the enigmatic intraplate volcanism in the Tristan da Cunha region requires knowledge of the tem- perature of the lithosphere and asthenosphere beneath it. We measured phase-velocity curves of Rayleigh waves using cross-correlation of teleseismic seismograms from an array of ocean-bottom seismometers around Tristan, constrained a region-average, shear-velocity structure, and inferred the temperature of the lithosphere and asthenosphere beneath the hotspot. The ocean-bottom dataset presented some challenges, which required data-processing and measurement approaches different from those tuned for land-based arrays of stations. Having derived a robust, phase-velocity curve for the Tristan area, we inverted it for a shear-wave velocity profile using a probabilistic (Markov chain Monte Carlo) approach. The model shows a pronounced low-velocity anomaly from 70 to at least 120 km depth. VS in the low velocity zone is 4.1–4.2 km/s, not as low as reported for Hawaii (~4.0 km/s), which probably indicates a less pronounced thermal anomaly and, possibly, less partial melting. Petrological modeling shows that the seismic and bathymetry data is consistent with a moderately warm mantle (mantle potential temperature of 1420–1440ºC, an excess of about 85–105ºC compared to the global average) and a melt fraction smaller than 1%. Both purely seismic inversions and petrological modeling indicate a lithospheric thickness of 65–70 km, consistent with recent estimates from receiver functions. The presence of warmer-than-average asthenosphere beneath Tristan is consistent with a hot upwelling (plume) from the deep mantle. However, the excess temperature we determine is smaller than that reported for some other major hotspots, in particular Hawaii.