In this paper, a modified ensemble randomized maximum-likelihood (EnRML) algorithm has been developed to estimate three-phase relative permeabilities with consideration of the hysteresis effect by reproducing the actual production 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 first used to represent the three-phase relative permeabilities, the coefficients of which can be automatically adjusted until production history is matched. A damping factor is introduced as an adjustment to the step length because a reduced step length is commonly required if an inverse problem is sufficiently nonlinear. A recursive approach for determining the damping factor has been developed to reduce the number of iterations and the computational load of 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 method and an indirect-restart method for numerical simulations, we optimize the restart method used for a specific problem. Subsequently, we validate the proposed methodology by use of a synthetic water-alternating-gas (WAG) displacement experiment and then extend it to match laboratory experiments. The proposed technique has proved to efficiently determine the three-phase relative permeabilities for the WAG processes with consideration of the hysteresis effect, whereas 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 with 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 use of the direct-restart method, whereas the indirect-restart method fails to minimize the uncertainties associated with the model variables representing three-phase relative permeabilities.