The initial structures for the search for the global minimum of TiO2 nanoclusters were generated by combining a tree growth (TG) algorithm with a hybrid genetic algorithm (HGA). In the TG algorithm, the clusters grow from a small seed to the size of interest stepwise. New atoms are added to the smaller cluster from the previous step, by analogy to new leaves grown by a tree. The addition of the new atoms is controlled by predefined geometry parameters to reduce the computational cost and to provide physically meaningful structures. In each step, the energies for the various generated structures are evaluated, and those with the lowest energies are carried into the next step. The structures that match the formulas of interest are collected as HGA candidates during the various steps. Low energy candidates are fed to the HGA component to search for the global minimum for each formula of interest. The lowest energy structures from the HGA are then optimized by using density functional theory to study the dissociation energies of the clusters and the evolution in the structure as the size of the cluster increases. The optimized geometries of the (TiO2)n nanoclusters for n = 2-13, do not show the character of a TiO2 bulk crystal with a hexacoordinate Ti. The average clustering energy ⟨ΔEn⟩ converges slowly to the bulk value for rutile. The TiO2 dissociation energies for (TiO2)n clusters approach the bulk value for rutile more quickly but show larger variations. The (TiO2)12 cluster appears to be quite stable, and the (TiO2)13 cluster is quite unstable on a relative scale.