Well testing is a powerful tool that can be used to study the characteristics of the reservoirs such as permeability, which are necessary to plan and develop their exploitation. However, conventional well test interpretation models do not apply to reservoirs containing non-Newtonian fluids as well as they do not consider heterogeneities of naturally fractured reservoirs (NFR), which leads to significant errors during interpretation. Another important factor that must be considered is the pressure sensitivity of the permeability in NFR because it can significantly affect the pressure transient response. Nevertheless, no researcher has investigated the effect of pressure-sensitivity of the permeability on the pressure response of NFR in presence of non-Newtonian fluids. Therefore, the main objective of this study was to develop a new physical and mathematical model to study the pressure transient behavior of NFR systems whose permeabilities are dependent on pressure and that are represented by fractal geometry, to consider heterogeneities of the fractured media, in presence of non-Newtonian fluids. A solution for the model was obtained by applying Pedrosa´s transformation, perturbation theory, Laplace transformation, theory of the generalized Bessel equation, and Sthefest´s numerical inversion algorithm. Thus, the solution to this problem was validated with previous work thoroughly. Then, the type curves of the model were built and the pressure transient behavior of the model was analyzed and discussed. The effects of parameters such as flow behavior index, fractal dimension, interconnectivity index, storage capacity coefficient, interporosity flow coefficient, skin factor, dimensionless permeability modulus, and dimensionless outer radius were discussed. A simulated case study was also presented, demonstrating the importance of properly choosing the parameters of the model to determine the properties of a formation from well test data. Finally, the major contribution of this work is coupling a NFR model with the fractal geometry of fractures, the rheological behavior of non-Newtonian fluids, and pressure sensitivity of the permeability into a completer and more generalized model to determine how much these factors impact the pressure response of a formation.