Deep fractured-porous carbonate reservoirs used for underground gas storage (UGS) experience simultaneous changes in temperature and effective stress during cyclic injection and withdrawal, so predicting permeability evolution is essential for evaluating long-term injectivity and deliverability. Using the Xiangguosi UGS as the engineering background, we measured steady-state gas permeability of three fractured-porous carbonate cores under representative conditions (20–80 °C; 15–35 MPa). Permeability decreases nonlinearly under coupled loading: changing temperature or effective stress alone typically reduces permeability by 30–70%, while the maximum reduction under concurrent increases in both variables exceeds 80% relative to the reference condition. An exponential model was fitted to quantify the decay parameter of permeability with effective stress (0.038–0.046 MPa⁻¹) and with temperature (0.016–0.020 °C⁻¹). In addition, the temperature-related exponential decay parameter decreases with increasing effective stress, because compliant fractures and larger pores are progressively pre-closed, weakening the permeability response to temperature. Finally, we propose a parsimonious separable exponential model that reproduces the measurements with a mean relative error below 12%, providing a practical constitutive relation for multiphysics simulations of UGS in fractured-porous carbonates.