A novel, simple, economical, and time effective method to estimate the anisotropic permeability of the coals is presented in this paper. This method estimates the coal’s anisotropic permeability by avoiding the tedious experimentation using triaxial permeameter or history matching exercises. This method calculates the absolute magnitude of the permeability of the sample. In this regard it is unlike other analytical permeability models, such as given by Palmer and Mansoori (1998) and Shi and Durucan (2014), that only calculate the permeability ratio (k/k0). The motivation is to find a method by which the permeability of the coal may be determined with reasonable accuracy by using only two easy measurements: 1) Mercury Intrusion Porosimetry (MIP) and; 2) Anisotropic stress-strain (σ-ε) measurement. The main blocks of the method are based on 1) cleat size which is obtained from MIP and randomly allocated to form flow-channels/cleats through the coal; 2) these cleats form parallel paths in the orthogonal face and butt cleat directions which provide the permeability; and 3) the cleat width (b) is stress dependent. This method is further validated by comparing with the experimentally measured stress-dependent permeability of Surat Basin (Australia) coal and a German coal in face cleat and butt cleat directions.