Reefs in the Browse Basin on the Australian North West Shelf typically have strong lateral velocity inhomogeneity on the reef flanks and produce an irregular sea-floor topography. The combination of these two factors reduces the effectiveness of conventional velocity analysis as moveout on common midpoint (CMP) gathers is no longer hyperbolic. Consequently, the velocity structure on the reef flanks cannot be resolved properly. An accurate velocity structure is needed for these reefs if seismic data acquired in the vicinity are to be migrated correctly. Tomographic velocity analysis, using a simultaneous iterative reconstruction technique (SIRT), was found to improve the velocity analysis of the reef when compared to conventional analysis. However, the reef's profile and rapid internal velocity gradients prevent accurate raypath determination. This technique can be further improved by preconditioning the data with wave-equation datuming. The water is replaced with an average reef velocity by downward and upward continuation. This effectively removes most of the raypath distortions resulting from ray bending at the sea floor, thus reducing the nonlinearity of the forward modeling and improving the convergence of an iteratively linearized inversion. The velocities obtained from this method give an accurate picture of the reef's internal velocity structure, as well as the lower portion of the seismic section below the reef.