We study the effect of size on the vibrational modes and frequencies of nanoparticles, by applying a newly developed, robust, and efficient first-principles-based method that we present in outline. We focus on rutile TiO2, a technologically important material whose bulk exhibits a softening of a transverse acoustic mode close to , which becomes unstable with the application of negative pressure. We demonstrate that, under these conditions, nanoparticles above a critical size exhibit unstable localized modes and we calculate their characteristic localization length and decomposition with respect to bulk phonons. We propose that such localized soft modes could initiate coherent structural phase transformations in small nanoparticles above a critical size.