Permeability is one of the most important parameters to evaluate gas production in shale reservoirs. Because shale permeability is extremely low, gas is often used in the laboratory to measure permeability. However, the measured apparent gas permeability is higher than the intrinsic permeability due to the gas slippage effect, which could be even more dominant for materials with nanopores. Increasing gas pressure during tests reduces gas slippage effect, but it also decreases the effective stress which in turn influences the permeability. The coupled effect of gas slippage and effective stress on shale permeability remains unclear. Here we perform laboratory experiments on Longmaxi shale specimens to explore the coupled effect. We use the pressure transient method to measure permeability under different stress and pressure conditions. Our results reveal that the apparent measured permeability is controlled by these two competing effects. With increasing gas pressure, there exists a pressure threshold at which the dominant effect on permeability switches from gas slippage to effective stress. Based on the Klinkenberg model, we propose a new conceptual model that incorporates both competing effects. Combining microstructure analysis, we further discuss the roles of stress, gas pressure and water contents on gas permeability of shale.