Many exploration and drilling applications would benefit from a robust method of integrating vertical seismic profile (VSP) and seismic data to estimate interval velocity. In practice, both VSP and seismic data contain random and correlated errors, and integration methods which fail to account for both types of error encounter problems. We present a nonlinear, tomography-like least-squares algorithm for simultaneously estimating an interval velocity from VSP and seismic data. On each nonlinear iteration of our method, we estimate the optimal shift between the VSP and seismic data and subtract the shift from the seismic data. In tests, our algorithm is able to resolve an additive seismic depth error, caused by a positive velocity perturbation, even when random errors are added to both seismic and VSP data.