We report on the investigation of temperature dependent optical dephasing of single terrylene molecules in a p-terphenyl host crystal using two different techniques. The temperature dependence of the optical linewidth between 2 and 7.2 K can be described by an exponentially activated process with an activation energy Delta E = 18 +/- 2 cm(-1), which is attributed to optical dephasing of the electronic transition by scattering of a pseudolocal mode. By measuring the fluorescence intensity autocorrelation function we demonstrate that the dephasing time of a single terrylene molecule can also be extracted from coherent transients (Rabi oscillations) appearing in the correlation function in the nanosecond time regime. These oscillations experience an increased damping at temperatures above 2 K due to pseudolocal mode-induced pure dephasing.