In this paper, a modified ensemble randomized maximum likelihood (EnRML) algorithm has been developed to estimate three-phase relative permeabilities with consideration of hysteresis effect by reproducing the actualproduction data. Ensemble-based history matching uses an ensemble of realizations to construct Monte Carlo approximations of the mean and covariance of the model variables, which can acquire the gradient information from the correlation provided by the ensemble. A power-law model is firstly utilized to represent the three-phase relative permeabilities whose coefficients can be automatically adjusteduntil production history is matched. A damping factor is introduced as an adjustment to the step length since a reduced step length is commonly required if an inverse problem is sufficiently nonlinear. Arecursive approach for determining the damping factor has been developed to reduce the number of iterations and the computational loadof the EnRML algorithm. The restart of reservoir simulations for reducing the cost of reservoir simulations is of significant importance for the EnRML algorithm where iterations are inevitable. By comparing a direct-restart methodand an indirect-restart method for numerical simulations, we optimize the restart method used for a specific problem. Subsequently, we validate the proposed methodologyby using a synthetic water-alternating-gas (WAG) displacement experiment and then extend it to match laboratory experiments. The proposed technique has proved toefficientlydetermine the three-phase relative permeabilities for the WAG processes with consideration of the hysteresis effect, while history matching results are gradually improved as more production data are taken into account. The synthetic scenarios demonstrate that the recursive approach saves 33.7% of the computational expense compared to the trial-and-error method when the maximum iteration is 14. Also, the consistency between the production data and model variables has been well maintained during the updating processes by using the direct-restart method, whereas the indirect-restart method fails to minimize the uncertainties associated with the model variables representing three-phase relative permeabilities.