We develop a waveform-tomography method for estimating the velocity distribution that minimizes the waveform misfit between the predicted and observed early arrivals in space-time seismograms. By fitting the waveforms of early arrivals, early arrival waveform tomography (EWT) naturally takes into account more general wave-propagation effects compared to the high-frequency method of traveltime tomography, meaning that EWT can estimate a wider range of slowness wavenumbers. Another benefit of EWT is more reliable convergence compared to full-waveform tomography, because an early-arrival misfit function contains fewer local minima. Synthetic test results verify that the waveform tomogram is much more accurate than the traveltime tomogram and that this algorithm has good convergence properties. For marine data from the Gulf of Mexico, the statics problem caused by shallow, gassy muds was attacked by using EWT to obtain a more accurate velocity model. Using the waveform tomogram to correct for statics, the stacked section was significantly improved compared to using the normal move-out (NMO) velocity, and moderately improved compared to using the traveltime tomogram. Inverting high-resolution land data from Mapleton, Utah, showed an EWT velocity tomogram that was more consistent with the ground truth (trench log) than the traveltime tomogram. Our results suggest that EWT can provide supplemental, shorter-wavelength information compared to the traveltime tomogram for both shallow and moderately deep seismic data.