The relative stability of TiO2 in the rutile and anatase structure is wrongly described by density functional theory in various local, semilocal, or even hybrid functional approximations. In this work, we have found that by considering high-order correlations in the adiabatic connection fluctuation-dissipation theory with the random phase approximation (ACFDT-RPA), rutile is correctly predicted to be more stable than anatase, which can be physically attributed to different characters in the electronic band structure of rutile and anatase, including, in particular, that rutile has a smaller band gap than anatase. We further consider the zero-point energy and finite-temperature effects based on the harmonic approximation, and we found that the inclusion of the zero-point energy correction can further increase the relative stability of rutile, and leads to a better quantitative agreement with available experimental measurements. Our study indicates the importance of considering high-order dynamical correlation effects to correctly predict the relative phase stability of polymorphic materials, especially for those systems in which the less stable phase as predicted by conventional local, semilocal or even hybrid density functional approximations has a smaller band gap than the more stable one.