A method which utilizes the lateral offset information obtained by comparing swath bathymetric data at track crossover points as a further constraint on the navigation is presented. The method, based on generalized least squares inversion theory, derives a new navigational solution that minimizes the overall misfit between the pairs of topography at crossovers while trying to remain smooth and close to the starting model. To achieve a high numerical efficiency during inversions of large matrices, we employed sparse matrix algorithms. The inversion scheme was applied to a set of Sea Beam data collected over the East Pacific Rise near 9° 30' N in early 1988 at the time when the Global Positioning System had limited coverage. The starting model was constructed by taking evenly spaced samples of positions along the tracklines. For each one of the 361 crossovers, we gridded the bathymetric data around the crossover point compared the gridded maps, and calculated the offset and uncertainty associated with this estimation. A suite of inversion solutions were obtained depending on the choice of three free parameters (that is, the a priori model variance, the correlation interval of a priori model, and the trade-off coefficient between fitting the data and remaining close to the a priori model). The best solution was chosen as one that minimizes both the Sea Beam topography and free-air gravity anomaly differences at crossovers. The improvement was significant; the initial rms mismatch between the tracks and free-air gravity anomalies at crossovers was reduced from 610m to 75m and from 2.5mGal to 1.9mGal, respectively.