By means of spin-polarized low-energy electron microscopy, we show that the magnetic easy axis of one to three atomic-layer thick cobalt films on Ru(0001) changes its orientation twice during deposition: One-monolayer and three-monolayer thick films are magnetized in plane, while two-monolayer films are magnetized out of plane. The Curie temperatures of films thicker than one monolayer are well above room temperature. Fully relativistic calculations based on the screened Korringa-Kohn-Rostoker method demonstrate that only for two-monolayer cobalt films does the interplay between strain, surface, and interface effects lead to perpendicular magnetization.