Water-alternating gas (WAG) as a tertiary recovery method is applied to oil reservoirs at a later stage of reservoir life to more or less success depending on field and operation. Uncertainty in WAG optimization has been shown to be dependent on several factors including reservoir characterization, WAG timing, and its operation. In this paper, we comprehensively explore WAG optimization in the context of WAG operating parameters and hysteresis, the first paper to explore both simultaneously. WAG operating parameters have been analyzed and optimized at both the core and field scale with a general conclusion that the timing, miscibility, WAG ratio, cycle time, and number of cycles play a varying role in the WAG optimization. Reservoir characterization has considered well configuration, oil type, rock properties, and hysteresis in relative permeability. Due to the cyclic nature of WAG and the dependency of the relative permeability on the saturation history, the relative permeability hysteresis modeling plays a key role in WAG performance whereby different hysteresis models will predict different results, as shown in literature. In this paper, we consider the choice of the hysteresis model and WAG operating parameters on WAG optimization. First, a sensitivity analysis is performed to evaluate the effect of hysteresis models (no hysteresis, Carlson, and Killough) on a large number of WAG development scenarios sampled by the Latin hypercube sampling method. Next, optimizations were conducted to compare and analyze the optimum recovery factor and corresponding optimal WAG operating parameters for various combinations of hysteresis models. The results of the study indicate that excluding hysteresis modeling from simulations would likely lead to a higher predicted produced volume of the nonwetting phases, that is, oil and gas, and a lower predicted produced volume of the wetting phase, that is, water. Also, the optimal recovery factor as well as the optimal WAG operating parameters can be significantly affected by the choice of the hysteresis models.