The solid phase transition of TiO2, in particular anatase to rutile, has been extensively studied in the past 30 years. To seek the nucleation site at the beginning of phase transition is highly challenging, which asks for new theoretical techniques with high spatial and temporal resolution. This work reports the first evidence on the atomic structure of the nucleation sites in the TiO2 anatase-to-rutile phase transition. Novel automated theoretical methods, namely stochastic surface walking based pathway sampling methods, are utilized to resolve the lowest energy pathways at the initial stage of phase transition. We show that among common anatase surfaces, only the (112) ridged surface provides the nucleation site for phase transition, which can lead to the formation of both TiO2-II and brookite thin slabs. The TiO2-II phase is kinetically preferred product; the propagation into the subsurface is still hindered by high barriers that is the origin for the slow kinetics of nuclei formation. The rutile nuclei are thus not rutile phase but nascent metastable TiO2-II phase in an anatase matrix. The phase transition kinetics is found to be sensitive to the compressive strain and the crystallographic directions. The results rationalize the size and morphology dependence of the anisotropic phase transition kinetics of anatase particles and could facilitate the rational design of material via controlled solid phase transition.