We present a systematic ab initio study of antiferrodistortive (AFD) order in Ruddlesden-Popper (RP) phases of strontium titanate, Sr1+n Ti n O3n+1, as a function of both compressive epitaxial strain and phase number n. We find all RP phases to exhibit AFD order under a significant range of strains, recovering the AFD order of bulk SrTiO3 as ∼1/n2. A Ginzburg-Landau Hamiltonian including interoctahedral interactions reproduces our ab initio results well, opening a pathway to understanding other nanostructured perovskite systems. © 2010 The American Physical Society.