Full-waveform inversion (FWI) tries to estimate velocity models of the subsurface with improved accuracy and resolution compared to conventional methods. To be successful, it needs input data that is rich in low frequencies and possibly characterized by long source-to-receiver offsets. The correct solution of the inverse problem by means of local methods is facilitated if the starting model lies in the “valley” of the cost-function global minimum. We explore the possibility of relaxing this requirement by using genetic algorithms, a stochastic optimization method, as the driver of the FWI (GA FWI). However, stochastic methods are affected by the “curse of dimensionality,” meaning that they require huge and sometimes even unaffordable computer resources for inverse problems with many unknowns and costly forward modeling. Therefore, we need to adopt proper stratagems in the inversion and limit our goal to the estimation of a velocity macromodel that is of a model with only the long-wavelength velocity structures, which could eventually act as the starting model for a local, higher-resolution gradient-based inversion. To this end, in the GA FWI we parametrize the subsurface with two grids: (1) a coarse grid with widely spaced nodes, that is unknowns, for the inversion, and (2) a fine grid with shorter spacing for the modeling. As a side result, we can also have an estimate of the uncertainty at the solution nodes of the grid. The approach we discuss is 2D acoustic in the time domain, with finite difference forward modeling. The examples we show refer to the Marmousi model and to a marine field data set.