We present a new history matching method based on a Genetic Algorithm to estimate three-phase k (r) (relative permeability) from unsteady-state coreflood experiments. In this method, relative permeabilities (k (r)) are represented by quadratic B-Spline functions. Adjustable coefficients in k (r) functions are changed in an iterative process to minimize an objective function. The objective function is defined as the difference between the measures and simulated values of the pressure drop across the core and fluids recovery during the experiment. One of the main features of this approach is that water and gas relative permeabilities (k (rw) and k (rg)) are assumed to be functions of two independent saturations as opposed to most of the existing empirical k (r) models in which k (rw) and k (rg) are assumed to be only dependent of their own saturations. Another important aspect of this algorithm is that it considers inequality constrains to ensure that physically acceptable k (r) curves are maintained throughout the iterative optimization process. A three-phase coreflood simulator has been developed based on this methodology that generates best k (r) values by matching experimental data. The integrity of the developed software was first successfully verified by using two sets of experimental three-phase k (r) data published in the literature. Then, the results of some three-phase coreflood experiments carried out in our laboratory were used to obtain three-phase k (r) curves by this approach.