The prediction of porosity is achieved by using available core and log data; however, the estimation of permeability is limited to the scare core data. Hence, porosity and saturation data through the framework of flow units can be used to make an estimation of reservoir permeability. The purpose of this study is to predict the permeability of a carbonate gas reservoir by using physical-based empirical dependence on porosity and other reservoir rock properties. It is emphasized that this new relationship has a theoretical background and is based on molecular theories. It is found out that if rock samples with different types are separated properly and samples with similar fluid-flow properties are classified in the same group, then this leads to finding an appropriate permeability/porosity relationship. In particular, the concept of hydraulic flow units (HFU) is used to characterize different rock types. This leads to a new physical-based permeability/porosity relationship that has two regression constants which are determined from the HFU method. These coefficients, which are obtained for several rock types in this study, may not be applicable to other carbonate rocks; but, by using the general form of the model presented here, based on the HFU method, one may obtain the value of these coefficients for any carbonate rock types. Finally, we used the data of cored wells for the validation of the permeability results.