Particle velocity is an important parameter for analyzing the propagation law of stress waves in a solid medium. Combining the laser Doppler effect and an all-fiber interferometric velocimetry system, a measurement method of stress wave particle velocity in solid medium based on fiber coated probe was proposed. The optical fiber coated probe was embedded in the polymethyl methacrylate (PMMA) at the same radius from the burst center, and the miniature explosive ball with 0.125 g TNT equivalent was used as the explosion source to fill in the center cavity and generate stress wave. Based on the time-frequency analysis method of the short-time Fourier transform, the velocity of the optical fiber end surface could be calculated from the collected signal, and then the medium particle velocity could be deduced. The experimental results show that the velocity of the data measured by different fiber coated probes is 22.648 m/s and 23.505 m/s, respectively. The relative difference between the resulting particle velocity and the data obtained by the traditional circular electromagnetic particle speedometer method is less than 5.00%, which indicates the feasibility of the proposed method.