Microbial enhanced coalbed methane (ME-CBM) recovery is critically examined as a viable technology for natural gas recovery from coalbed methane (CBM) reservoirs. Since the majority of gas-in-place (GIP) is stored as an adsorbed phase in fine pores of coal matrix, the nano-pore structure directly influences gas storage and transport properties. Only limited studies have quantified the alteration of the nano-pore structure due to ME-CBM treatment. This study examines the evolution of the pore structure using a combination of small angle X-ray scattering (SAXS), low-pressure N2 and CO2 adsorption (LPGA) and high-pressure methane adsorption methods. The results show that the surface fractal dimension decreases for the two bioconverted coals compared to the untreated coal. After bio-treatment, the mesopore surface area and pore volume decrease with the average pore diameter increases, while the micropore surface area increases with pore volume decreases. Both inaccessible meso-/micropore size distributions decrease after bioconversion, while the accessible micropore size distribution increases, making a portion of closed micropore network accessible. In addition, the methane adsorption capacities increase after bio-treatment, which is confirmed by the increase of micropore surface area. A conceptual physical model of methanogenesis is proposed based on the evolution of the pore structure.