We address the problem of velocity estimation in heterogeneous media using a combination of nonlinear inversion and migration velocity analysis. In velocity estimation, the travel time information in seismic reflection data are nonlinearly related to the velocity perturbations in the subsurface. By taking a functional of seismic traces, the migrated data themselves, we define a misfit criterion which greatly reduces the oscillatory nature of the objective function. Migration is inherently a smoothing process; it collapses diffractions, focuses reflected energy, and suppresses random noise. We use the lateral consistency of reflectors after migration as a measure of model misfit. If we compare one migrated shot record with an adjacent record, the misfit will be only slightly affected by large velocity variations even though reflectors may show large errors in depth positioning. The closer the spacing between shot records the smaller the variations in misfit; hence the smoother the objective function. We search for global minima of the objective function thus defined, using a genetic algorithm (GA) and a linearized inversion scheme. We illustrate the techniques and results from the algorithms by applying them to a realistic scale synthetic data set. As expected, the success of a linearized scheme depends strongly on the starting model while GA does not depend on the choice of the initial population of models. GA is computationally intensive but our choice of spline parameterization reduces the number of model parameters significantly and makes the algorithm computationally tractable for real earth problems. ¿ American Geophysical Union 1993