With respect to the sharp increase in population all around the world, more and more energy and fuels are expected to achieve the counterbalance between supply and demand. Deeply attracted by its considerable and prospect recovery reserve, the exploitation, development and related research contents regarding coalbed methane (CBM), i.e., one of the unconventional gas reservoirs, are currently heat and essential topics. Without any doubt, precise determination of coal permeability will dramatically contribute to the development efficiency of CBM reservoirs. It should be noted that the permeability in CBM reservoirs possesses unique heterogeneous characteristics, especially for the different permeability at directions of face cleats and butt cleats, which will inevitably result in greatly shape-change for fluid flow field and eventually the production performance. To my best knowledge, nearly all the previous methods proposed for evaluating coal permeability assume the homogeneous permeability feature in CBM reservoirs, which show fairly great discrepancy compared with that of the realistic situation. In this work, in order to address this urgent issue, a novel permeability evaluation method is developed for the first time, which is able to generate precisely heterogeneous characteristics of coal permeability based on the water production rate versus production time curve at the early production stage. First of all, considering both orthotropic heterogeneous permeability and pressure propagation behavior in CBM reservoirs, single water phase productivity equation is seriously derived. Secondly, for simply usage purpose in field application, the obtained equation is transformed through linearization treat. Finally, combining the water production performance with the linearized equation, efficient iteration calculation procedures are given to determine the heterogeneous permeability feature. Also, the skin factor of corresponding CBM well can be determined. The applicability and accuracy of the proposed method have been successfully verified through field application. In sum, the proposed method can serve as a simple as well as an accurate tool to determine the crucial heterogeneous permeability feature in CBM reservoirs. More importantly, during the determination process, the method just requires the water production performance at the early production stage, which means that the obtained permeability characteristics can be utilized to guide production strategy adjustment in the following gas production stage. As a result, the proposed method can be regarded as a necessary preparatory work before gas production takes place in CBM reservoirs, which will play a positive and active role in optimization of ultimate gas recovery and well configuration.