Seismic reflection data contain information on small-scale impedance variations and a smooth reference velocity model. Given a reference velocity model, the reflectors can be obtained by linearized migration-inversion. If the reference velocity is incorrect, the reflectors obtained by inverting different subsets of the data will be incoherent. We propose to use the coherency of these images to invert for the background velocity distribution. We have developed a two-step iterative inversion method in which we separate the retrieval of small-scale variations of the seismic velocity from the longer-period reference velocity model. Given an initial background velocity model, we use a waveform misfit-functional for the inversion of small-scale velocity variations. For this linear step we use the linearized migration-inversion method based on ray theory that we have recently developed with Lambare and Virieux. The reference velocity model is then updated by a Monte Carlo inversion method. For the nonlinear inversion of the velocity background, we introduce an objective functional that measures the coherency of the short wavelength components obtained by inverting different common shot gathers at the same locations. The nonlinear functional is calculated directly in migrated data space to avoid expensive numerical forward modeling by finite differences or ray theory. Our method is somewhat similar to an iterative migration velocity analysis, but we do an automatic search for relatively large-scale 1-D reference velocity models. We apply the nonlinear inversion method to a marine data set from the North Sea and also show that nonlinear inversion can be applied to realistic scale data sets to obtain a laterally heterogeneous velocity model with a reasonable amount of computer time.