This paper presents a novel implementation for evolutionary algorithms in oil and gas reservoirs history matching problems. The reservoir history is divided into time segments. In each time segment, a penalty function is constructed that quantifies the mismatch between the measurements and the simulated measurements, using only the measurements available up to the current time segment. An evolutionary optimization algorithm is used, in each time segment, to search for the optimal reservoir permeability and porosity parameters. The penalty function varies between segments; yet the optimal reservoir characterization is common among all the constructed penalty functions. A population of the reservoir characterizations evolves among subsequent time segments through minimizing different penalty functions. The advantage of this implementation is two fold. First, the computational cost of the history matching process is significantly reduced. Second, problem constraints can be included in the penalty function to produce more realistic solutions. The proposed concept of dynamic penalty function is applicable to any evolutionary algorithm. In this paper, the implementation is carried out using genetic algorithms. Two case studies are presented in this paper: a synthetic case study and the PUNQ-S3 field case study. A computational cost analysis that demonstrates the computational advantage of the proposed method is presented.