The microscopic mechanism of proton diffusion in the protonic conductor Sc-doped SrTiO3 is studied by ab initio molecular dynamics (MD) simulations based on the generalized gradient-corrected density functional theory (DFT). It is shown that the frequencies of the O-H stretching vibration are in good agreement with the infrared transmission measurements, and that the distortion of the oxygen sublattice around the oxygen vacancy enables the pathway of the proton diffusion between the second nearest neighbor O ions, which are never seen in the crystal without the oxygen vacancies.