Ensemble-based optimization methods are often efficiently applied to history-matching problems. Although satisfactory matches can be obtained, the updated realizations, affected by spurious correlations, generally fail to preserve prior information when using a small ensemble, even when localization is applied. In this work, we propose a multi-scale approach based on grid-adaptive second-generation wavelets. These wavelets can be applied on irregular reservoir grids of any dimensions containing dead or flat cells. The proposed method starts by modifying a few low frequency parameters (coarse scales) and then progressively allows more important updates on a limited number of sensitive parameters of higher resolution (fine scales). The Levenberg-Marquardt ensemble randomized maximum likelihood (LM-enRML) is used as optimization method with a new space-frequency distance-based localization of the Kalman gain, specifically designed for the multi-scale scheme. The algorithm is evaluated on two test cases. The first test is a 2D synthetic case in which several inversions are run using independent ensembles. The second test is the Brugge benchmark case with 10 years of history. The efficiency and quality of results of the multi-scale approach are compared with the grid-block-based LM-enRML with distance-based localization. We observe that the final realizations better preserve the spatial contrasts of the prior models and are less noisy than the realizations updated using a standard grid-block method, while matching the production data equally well.