Based upon spin-lattice interaction, we propose a theoretical model for the phonon Hall effect in paramagnetic dielectrics. The thermal Hall conductivity is calculated by using the Kubo formula. Our theory reproduces the essential experimental features of the phonon Hall effect discovered recently in ionic dielectric Tb$_3$Ga$_5$O$_{12}$, including the sign, magnitude and linear magnetic field dependence of the thermal Hall conductivity.