  We present the first systematic {\em ab initio} study of anti-ferrodistortive
(AFD) order in Ruddlesden-Popper (RP) phases of strontium titanate,
Sr$_{1+n}$Ti$_n$O$_{3n+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 bulk AFD order as $\sim 1/n^2$. A
Ginzburg-Landau Hamiltonian generalized to include inter-octahedral
interactions reproduces our {\em ab initio} results well, opening a pathway to
understanding other nanostructured perovskite systems.
