Determination of the long wavelength, or background, velocity structure is a critical step in prestack imaging. We have developed an efficient procedure for the solution of this non-linear inverse problem using a genetic algorithm (GA). In our approach velocities are described by splines; velocity values at spline nodes are the parameters in the inversion. We distinguish between primary nodes, affecting very long wavelength variation, and secondary nodes, describing more rapid change. The GA evolves a population of trial solutions, seeking out the globally fittest velocity model. Key to the method is the evaluation of fitness, which is carried out in three steps: (1) map migration of zero-offset traveltimes through the trial velocity model to identify the approximation locations of primary reflectors; (2) prestack Kirchhoff depth migration to generate image gathers in narrow depth windows centered on the predicted reflector locations; (3) calculation of horizontal semblance within the image gathers. For the correct velocity model, reflection events appear flat in each of the gathers; thus, by calculating horizontal semblance we obtain a measure of fitness for the GA. Since the migration is performed over a narrow depth range in the neighborhood of a given reflector, rays need only be traced from a small number of depth points for each gather; additional ray information can be efficiently obtained using paraxial approximations.