In order to analyze the stochastic responses of a train-bridge coupling system in high-speed railway, the pseudo-excitation method (PEM) was applied to transform a vertical track profile irregularity into the superposition of harmonic excitations at a series of frequency points to translate a non-stationary random vibration problem into a deterministic time history problem. The method of separate iteration was used to solve the equations for the coupling system. The maximum and minimum responses of the coupling system were obtained based on the thrice standard error principle. The change regularities of the stochastic responses under different train velocities were discussed. The results show that the vertical displacement and acceleration of car body have large randomness, and the vertical responses of the mid-span of a bridge and the vertical wheel/rail force are influenced by the deterministic load. Train velocity has a significant influence on the maximum vertical acceleration of the mid-span and the maximum and minimum vertical accelerations of the car body.