The effect of the nanostructure on the photochemistry of TiO2 is an active field of research owing to its applications in photocatalysis and photovoltaics. Despite this interest, little is known of the structure of small particles of this oxide with sizes at the nanometer length scale. Here we present a computational study that locates the global minima in the potential energy surface of Ti(n)O2n clusters with n = 1-15. The search procedure does not refer to any of the known TiO2 polymorphs, and is based on a novel combination of simulated annealing and Monte Carlo basin hopping simulations, together with genetic algorithm techniques, with the energy calculated by means of an interatomic potential. The application of several different methods increases our confidence of having located the global minimum. The stable structures are then refined by means of density functional theory calculations. The results from the two techniques are similar, although the methods based on interatomic potentials are unable to describe some subtle effects. The agreement is especially good for the larger particles, with n = 9-15. For these sizes the structures are compact, with a preference for a central octahedron and a surrounding layer of 4- and 5-fold coordinated Ti atoms, although there seems to be some energy penalty for particles containing the 5-fold coordinated metal atoms with square base pyramid geometry and dangling Ti=O bonds. The novel structures reported provide the basis for further computational studies of the effect of nanostructure on adsorption, photochemistry, and nucleation of this material.