Naturally Fractured Reservoirs (NFR) contain a significant amount of remaining petroleum reserves and are now being considered for water-alternating-gas (WAG) flooding as secondary or tertiary recovery. Reservoir simulation of WAG is very challenging even in non-fractured reservoirs because a proper set of saturation functions that describe the underlying physics is vitally important but associated with high uncertainty. For NFRs, another challenge is the upscaling of recovery processes, particularly the fracture-matrix transfer during three-phase flow, to the reservoir scale using dual-porosity or dual-permeability models. In this work, we approach a solution to this challenge by building models at various scales, starting from pore-scale to an intermediate scale then to the reservoir scale. We show how pore-network modelling and fine grid modelling where the fractures and matrix are represented explicitly can be used to increase the accuracy of numerical simulations at the field-scale in order to predict recoveries for NFR during WAG. We study the sensitivity to WAG design parameters as well as the impact of matrix wettability on recovery. We also compare the fine grid model with an equivalent dual-porosity model. Simulation at an intermediate scale showed at least 10% absolute change in recovery due to the choice of the empirical three-phase relative permeability model. In fine grid simulation with physically consistent pore-network derived three-phase relative permeability and capillary pressure, injected water and gas are predicted to displace each other, leaving oil behind, therefore reducing WAG efficiency. For this case, empirical models over-estimate recovery by 25%. Classical dual-porosity model over-estimates recovery during the early WAG cycles, and fails to adequately match recovery of the fine grid simulation. Our multi-scale simulation approach identifies important factors and uncertainties when considering WAG flooding in NFR. It provides a methodology through which WAG recovery can be estimated using available technology while preserving the pore-scale physics for three-phase flow, which are crucial to making reliable forecasts at the reservoir scale.