Abstract With the increased emphasis on accurately representing geological variability / uncertainty in modeling heterogeneous reservoirs, the goal of modern history matching methods is not only to reproduce the past production behavior; it also aims at preserving geological realism. However, in complex geological environments, with limited access to the subsurface (e.g. deepwater/turbidite systems), the geological scenario governing the spatial distribution of important reservoir properties such as facies type / permeability is uncertain. Indeed, with few wells and limited seismic resolution, an accurate determination of the geological depositional system may not be possible. In this paper, we propose a new history matching technique that can account for this first order uncertainty. At the same time, this method can be regarded as a way to reduce geological uncertainty by means of production data. To model geological scenario uncertainty we rely on the field of multiple-point geostatistics, where each scenario is quantitatively depicted by a training image, a fully explicit reservoir analog of sorts. Given a training image, a geological model realization can be stochastically generated using geostatistical algorithms. A discrete set of such scenarios is assumed available from a careful geological uncertainty study. To solve the inverse problem of history matching one can no longer rely on the classical optimization with gradient formulation, due to the inherently discrete nature of the problem. Instead, we rely on stochastic search methods (such as the Neighborhood Algorithm), that search in the space of all geologically plausible model realizations for those that history match by considering a ‘similarity’ measure between such plausible geological model realizations. We show that the production response in the space defined by a suitable similarity measure is structured, i.e. not random, hence optimization/history matching with stochastic search methods is effective. Several realistic synthetic reservoir applications are presented to illustrate this methodology.