Small polaron formation in transition metal oxides, like the prototypical material rutile TiO$_2$, remains a puzzle and a challenge to simple theoretical treatment. In our combined experimental and theoretical study, we examine this problem using Raman spectroscopy of photo-excited samples and real-time time-dependent density functional theory (RT-TDDFT), which employs Ehrenfest dynamics to couple the electronic and ionic subsystems. We observe experimentally the unexpected stiffening of the $A_{1g}$ phonon mode under UV illumination and provide a theoretical explanation for this effect. Our analysis also reveals a possible reason for the observed anomalous temperature-dependence of the Hall mobility. Small polaron formation in rutile TiO$_2$ is a strongly non-adiabatic process and is adequately described by Ehrenfest dynamics at time scales of polaron formation.