Induction of CD8+ T cell immunity is a key characteristic of an effective vaccine. For safety reasons, human vaccination strategies largely use attenuated nonreplicating or weakly replicating poxvirus-based vectors, but these often elicit poor CD8+ T cell immunity and might not result in optimal protection. Recent studies have suggested that virulence is directly linked to immunogenicity, but the molecular mechanisms underlying optimal CD8+ T cell responses remain to be defined. Here, using natural and recombinant vaccinia virus (VACV) strains, we have shown in mice that VACV strains of differing virulence induce distinct levels of T cell memory because of the differential use of TNF receptor (TNFR) family costimulatory receptors. With strongly replicating (i.e., virulent) VACV, the TNFR family costimulatory receptors OX40 (also known as CD134) and CD27 were engaged and promoted the generation of high numbers of memory CD8+ T cells, which protected against a lethal virus challenge in the absence of other mechanisms, including antibody and help from CD4+ T cells. In contrast, weakly replicating (i.e., low-virulence) VACV strains were poor at eliciting protective CD8+ T cell memory, as only the Ig family costimulatory receptor CD28 was engaged, and not OX40 or CD27. Our results suggest that the virulence of a virus dictates costimulatory receptor usage to determine the level of protective CD8+ T cell immunity.