To study the change and main control factors of the high-rank coal reservoir permeability in deep coal seams, permeability tests under different stresses and gas pressures were carried out in the laboratory. The development and distribution of nano-micro pores and fractures in the coal matrix were analyzed and observed by mercury intrusion porosimetry, gas adsorption, scanning electron microscope and computed tomography to reveal the permeability variation mechanism. The results showed that the initial permeability of the coal samples ranged from 0.0114 mD to 0.2349 mD when the effective stress was 0 MPa, and it clearly varied among different samples. The permeability of all the coal samples was very sensitive to the effective stress and decreased exponentially with the increase of the effective stress. The increase of the pore pressure also led to a decrease of the permeability, whereas the impact of the pore pressure on permeability was less obvious compared with the effective stress. Sub-nanopores, nanopores, micro-fractures and larger fractures are all developed in the coal samples. Connected larger fractures were the main gas migration channels in permeability determination, and the narrowing, disconnection, and closure of the fractures caused by the increase of the effective stress were the most important reasons for significant reduction of permeability.