A multiple time step (MTS) algorithm for trajectory surface hopping molecular dynamics has been developed, implemented, and tested. The MTS scheme is an extension of the ab initio implementation for Born-Oppenheimer molecular dynamics presented in the work of Liberatore et al. [J. Chem. Theory Comput. 14, 2834 (2018)]. In particular, the MTS algorithm has been modified to enable the simulation of non-adiabatic processes with the trajectory surface hopping (TSH) method and Tully's fewest switches algorithm. The specificities of the implementation lie in the combination of Landau-Zener and Tully's transition probabilities during the inner MTS time steps. The new MTS-TSH method is applied successfully to the photorelaxation of protonated formaldimine, showing that the important characteristics of the process are recovered by the MTS algorithm. A computational speed-up between 1.5 and 3 has been obtained compared to standard TSH simulations, which is close to the ideal values that could be obtained with the computational settings considered.