We determine the upper mantle seismological structure of the southwest Pacific by inverting complete regional seismograms recorded by the Southwest Pacific Seismic Experiment, a deployment of 12 broadband seismographs in the Fiji, Tonga, and Niue islands. We first present a method to invert entire seismic waveforms for a laterally homogeneous velocity structure. Partial derivatives are computed using an efficient reflectivity code for differential seismograms <Randall, 1994>, and a conjugate gradient method is used to perform the nonlinear inversion. Band pass-filtered (10--55 mHz) vertical and radial component seismograms, extending from the P arrival to the surface waves, are used to constrain the structure. Waveforms are selected to provide regional distance (400--1500 km) propagation paths predominantly within one of the tectonic regions of the southwest Pacific. Source depths ranging from 10 to 240 km allow the deeper regions of the model to be resolved with relatively short path lengths. Results show extremely large lateral variability in the upper mantle structure of the southwest Pacific. The inactive South Fiji Basin shows upper mantle velocities much lower than those previously observed for the Pacific lithosphere of a similar age. The North Fiji and Lau Basins, containing active back arc spreading systems, show upper mantle shear velocities as slow as 3.8 km s-1. The exceptionally low seismic velocities in the active back arc regions may represent the slowest upper mantle velocities in the world. The velocity difference between the active back arc basins and the old Pacific lithosphere immediately east of the Tonga Trench is maximum at 30--90 km depth, with a variation of ~18%, indicating partial melting in this depth range. Velocity heterogeneity of >4% extends to a depth of 170 km. Velocity structure below 220 km depth is poorly resolved, but there is some evidence of a 2% difference extending to depths of 350 km. ¿ 1997 American Geophysical Union