We present a nonlinear optimization method for two-dimensional velocity estimation in strongly heterogeneous media. We achieve this by designing a simulated-annealing algorithm to simultaneously maximize reflection coherency as well as minimize first-arrival travel time residuals. Relatively shallow velocity structure is constrained by first-arrival times, while coherency information from deeper reflections (if present) helps constrain deeper velocities. Prestack migration using the optimized velocities images reflections with greater continuity, compared with other velocity estimation methods. Using synthetic and real data we demonstrate that migrations through velocities obtained using our coherency criterion reconstruct basin-boundary structures more accurately than through those obtained using only first-arrival times. Images from shot gathers collected along COCORP Mojave line 5 across the Garlock fault in Cantil Valley, California show new evidence of links between Garlock fault branches and sub-horizontal structures in the upper crust. Imaging reflections and estimating velocities using coherency annealing is more effective and less expensive than picking reflection times from shot gathers recorded complex regions.¿ 1997 American Geophysical Union