To overcome the inaccuracy of the traditional transient pulse test, a new fractional derivative-based permeability estimation formula based on the transient pulse test is proposed to describe the pressure difference decay of a coal body subjected to mining-induced stresses. The permeability of coal specimens under mining disturbance conditions is measured using the MTS815 rock mechanics test system. The experimental results show that the transient pulse test based on the fractional derivative model provides a much better estimation of the coal specimen’s permeability than the conventional exponential decay model. Analyzing the evolution of the coal’s permeability shows that the permeability tends to decrease in the pre-peak compaction stage, following which it gradually increases in the plastic phase, and then increases sharply in the post-peak phase. The significance of the fractional derivative order γ is discussed, and its analysis shows that the solid-liquid interaction inside the specimen becomes complicated when the stress within the coal specimen changes.