The cleat compressibility of coal is a key parameter that is extensively used in modeling the coal reservoir permeability for Coal Bed Methane (CBM) recovery. Cleat compressibility is often determined from the permeability measurement made at different confining pressures but with a constant pore pressure. Hence, this parameter ignores the sorption strain effects on the cleat compressibility. By using the transient pulse decay (TPD) technique, this study presents the results from a laboratory characterization program using coal core drilled from different bedding directions to estimate gas permeability and coal cleat compressibility under different pore pressures while maintaining effective stress constant. Cleat compressibility was determined from permeability and sorption strain measurements that are made at different pore pressures under an effective stress constant. Results show that the cleat compressibility of coal increases slightly with the increase of pore pressure. Moreover, the cleat compressibility of Sample P (representing the face cleats in coal) is larger than that of Sample C (representing the butt cleats in coal). This result suggests that cleat compressibility should not be regarded as constant in the modeling of the CBM recovery. Furthermore, the compressibility of face cleats is considerably sensitive to the sorption-induced swelling/shrinkage and offers significant effects on the coal permeability.