Through INSTRON1304 electric hydraulic servo fatigue testing machine, the fatigue experiment of soil-cement is done, and the ultrasonic velocity of soil-cement under dynamic loading is obtained. The results show the ultrasonic wave velocity through the cemented soil samples free surface obviously attenuates as the cycles of the dynamic loading increases. Based on the damage variable defined by the ultrasonic wave velocity, the evolution equation of soil-cement accumulated fatigue damage is established. The equation indicates that the fatigue damage of soil-cement l under dynamic loading can obviously be divided into three stages: the initial rapid decay of the initial state, stability decay and rapid damage close to the destruction. The experiment results provide an important reference for non-destructive testing of soil-cement under dynamic loading.