Due to the complex and varied substrate environmental characteristics of cobalt-rich crusts and hydrothermal sulfide survey area in deep sea, a composite wheeled mining robot with active and passive over-obstacle capacity is designed. The mining robot is composed of 4-composite wheels and an integral articulated sealed compressive tank frame. A static model of the composite wheels structure is set up in the typical over-obstacle condition, to obtain its main structural parameters affecting over-obstacle capacity. Using MATLAB toolbox, the composite wheels structural parameters are optimized for design, so that the over-obstacle capacity is improved. Considering the complex and varied substrate environmental characteristics in deep sea, dynamics model of the optimized composite wheeled robot is set up, the simulation analysis with ADAMS is performed, and dynamic characteristics curve and mechanical characteristics curve of the mining robot are obtained in over-obstacle process. Through designing prototype and testing its over-obstacle capacity, it is shown that the mining robot has strong over-obstacle capacity and transit stability in the complex and varied deep sea substrate environment.