This paper discusses a novel workflow for history matching by perturbing the reservoir structural model constrained to prior geophysical and geological information. Our approach first models prior structural uncertainty related to geophysical processing and structural interpretations using geostatistical methods. Then, from the resulting large set of structural model realizations representing this prior structural uncertainty, the model realizations that match past production history are searched for using a stochastic search technique. In order to achieve an efficient search, the prior structural uncertainty models are embedded into a space defined with a “similarity distance”, i.e. a distance function which measures the similarity between any two reservoir geometry realizations. By choosing a proper distance function, production response from model realizations is spatially structured in this space, allowing a near-neighbor search such as the neighborhood algorithm (Sambridge, 1996). This workflow considers not only stochastically perturbed structural models around some reference interpretation, but also several structural scenarios with varying numbers and positions of fault blocks. A realistic case study is presented.