Protective T-cell memory has long been thought to reside in blood and lymph nodes, but recently the concept of immune memory in peripheral tissues mediated by resident memory T (T_RM) cells has been proposed^,,,,. Here we show in mice that localized vaccinia virus (VACV) skin infection generates long-lived non-recirculating CD8⁺ skin T_RM cells that reside within the entire skin. These skin T_RM cells are potent effector cells, and are superior to circulating central memory T (T_CM) cells at providing rapid long-term protection against cutaneous re-infection. We find that CD8⁺ T cells are rapidly recruited to skin after acute VACV infection. CD8⁺ T-cell recruitment to skin is independent of CD4⁺ T cells and interferon-γ, but requires the expression of E- and P-selectin ligands by CD8⁺ T cells. Using parabiotic mice, we further show that circulating CD8⁺ T_CM and CD8⁺ skin T_RM cells are both generated after skin infection; however, CD8⁺ T_CM cells recirculate between blood and lymph nodes whereas T_RM cells remain in the skin. Cutaneous CD8⁺ T_RM cells produce effector cytokines and persist for at least 6 months after infection. Mice with CD8⁺ skin T_RM cells rapidly cleared a subsequent re-infection with VACV whereas mice with circulating T_CM but no skin T_RM cells showed greatly impaired viral clearance, indicating that T_RM cells provide superior protection. Finally, we show that T_RM cells generated as a result of localized VACV skin infection reside not only in the site of infection, but also populate the entire skin surface and remain present for many months. Repeated re-infections lead to progressive accumulation of highly protective T_RM cells in non-involved skin. These findings have important implications for our understanding of protective immune memory at epithelial interfaces with the environment, and suggest novel strategies for vaccines that protect against tissue tropic organisms.