A new explosion-proof walking system was designed for the coal mine rescue robot (CMRR) by optimizing the mechanical structure and control algorithm. The mechanical structure innovation lies mainly in the dual-motor drive tracked unit used, which showed high dynamic performance compared with the conventional tracked unit. The control algorithm, developed based on decision trees and neural networking, facilitates autonomous switching between “Velocity-driven Mode” and “Torque- driven Mode”. To verify the feasibility and effectiveness of the control strategy, we built a self-designed test platform and used it to debug the control program; we then made a robot prototype and conducted further experiments on single-step, ramp, and rubble terrains. The results show that the proposed walking system has excellent dynamic performance and the control strategy is very efficient, suggesting that a robot with this type of explosion-proof walking system can be successfully applied in Chinese coal mines.