Once deep coal rock is disturbed by engineering operations, coal exhibits different initial damage degrees (IDDs), which may govern subsequent crack propagation and permeability evolution under cyclic stress. Therefore, cyclic loading and permeability tests, combined with acoustic emission (AE) and computed tomography (CT) scanning techniques, were conducted to systematically investigate the effects of the IDD on the crack propagation and permeability evolution of coal. The results indicated that high IDDs led to a significant decrease in the peak strength and deformation modulus of the coal samples and a significant increase in the dissipated energy percentage. Furthermore, AE analyses showed that the b value dropped from 1.863 to 0.784 and the energy critical index decreased, whereas the multifractal spectrum width and subset parameter increased, indicating a shift from small-scale microcracking to more complex, large-scale crack coalescence in coal specimens with higher IDDs. Permeability generally decreased with increasing stress, but coal specimens with high IDDs exhibited a transient permeability recovery at high stress levels and a larger post-failure permeability enhancement, reflecting the competition between compaction and crack propagation. Moreover, CT-based analysis shows that crack volume percentage increased from 2.821% to 8.968% and fractal dimension rose from 2.011 to 2.052 with increasing IDDs, correlating well with permeability evolution. These results provide useful implications for stability and permeability characteristics in coal reservoirs and deep geo-energy engineering.