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 (TRM) cells has been proposed1,2,3,4,5. Here we show in mice that localized vaccinia virus (VACV) skin infection generates long-lived non-recirculating CD8+ skin TRM cells that reside within the entire skin. These skin TRM cells are potent effector cells, and are superior to circulating central memory T (TCM) 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+ TCM and CD8+ skin TRM cells are both generated after skin infection; however, CD8+ TCM cells recirculate between blood and lymph nodes whereas TRM cells remain in the skin. Cutaneous CD8+ TRM cells produce effector cytokines and persist for at least 6 months after infection. Mice with CD8+ skin TRM cells rapidly cleared a subsequent re-infection with VACV whereas mice with circulating TCM but no skin TRM cells showed greatly impaired viral clearance, indicating that TRM cells provide superior protection. Finally, we show that TRM 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 TRM 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.