Bottom-up and top-down derived nanoparticle structures refined by accurate ab initio calculations are used to investigate the size dependent emergence of crystallinity in titania from the monomer upwards. Global optimisation and data mining are used to provide a series of ( TiO2) N global minima candidates in the range N = 1-38, where our approach provides many new low energy structures for N > 10. A range of nanocrystal cuts from the anatase crystal structure are also considered up to a size of over 250 atoms. All nanocrystals considered are predicted to be metastable with respect to non-crystalline nanoclusters, which has implications with respect to the limitations of the cluster approach to modelling large titania nanosystems. Extrapolating both data sets using a generalised expansion of a top-down derived energy expression for nanoparticles, we obtain an estimate of the non-crystalline to crystalline crossover size for titania. Our results compare well with the available experimental results and imply that anatase-like crystallinity emerges in titania nanoparticles of approximately 2-3 nm diameter.