Elucidating the details of electron-phonon coupling in semiconductors and insulators is a topic of pivotal interest, as it governs the transport mechanisms and is responsible for various phenomena such as spectral-weight transfers to phonon sidebands and self-trapping. Here, we investigate the influence of the electron-phonon interaction on the excitonic peaks of rutile TiO2, revealing a strong anisotropic polarization dependence with increasing temperature, namely, an anomalous blue shift for light polarized along the a axis and a conventional red shift for light polarized along the c axis. By employing many-body perturbation theory, we identify two terms in the electron-phonon interaction Hamiltonian that contribute to the anomalous blue shift of the a-axis exciton. Our approach paves the way to a complete ab initio treatment of the electron-phonon interaction and of its influence on the optical spectra of polar materials.