The permeability (K) of tight carbonate rocks is important to maximize the efficiency of hydrocarbon production and overall reservoir management. While such property is crucial for engineering design, conducting experimental tests to determine K can be both time-consuming and expensive. As such, reliable and high-fidelity models derived with soft computing techniques become useful for estimating K. Using a data set containing samples from 130 data points published in the literature, this work developed a sensitivity-driven evolutionary polynomial regression (EPR) model to predict K. The model computes the permeability, log10K (mD), as a function of three explanatory variables: porosity, ϕ (-), formation factor, F (-), and the characteristic pore throat diameter, dPT (m). One unique feature of our approachis that it considers the physical meaning of the variables that influence the investigated phenomenon during the construction of the model. Verification of the methodology was carried out using split-sampling cross-validation. The developed model showed attributes such as parsimony (lower number of parameters and input variables), good predictive capability (accurate tracking observed log10K), generalization ability (preserving physical meaning), and robustness (consistent performance under cross-validation). Sensitivity analysis revealed that the model can adequately simulate the increase in K with increasing ϕ and dPT, as well as its capacity to capture the non-linear relationship between log10K and F. Comparison of simulated K-values with results of models published in the literature, further validated the ability of our optimum EPR model structure. The proposed model shows potential as a promising method to estimate the permeability of tight carbonate rocks.