Adenoviral vectors have long been forerunners in the development of effective CD8 T cell-based vaccines; therefore, it is imperative that we understand the factors controlling the induction of robust and long-lasting transgene-specific immune responses by these vectors. In this study, we investigated the organ sites, molecules, and cell subsets that play a critical role in the priming of transgene-specific CD8 T cells after vaccination with a replication-deficient adenoviral vector. Using a human adenovirus serotype 5 (Ad5) vector and genetically engineered mice, we found that CD8(+) and/or CD103(+) dendritic cells in the draining lymph node played a critical role in the priming of Ad5-induced CD8 T cell responses. Moreover, we found that CD80/86, but not CD28, was essential for efficient generation of both primary effectors and memory CD8 T cells. Interestingly, the lack of CD28 expression resulted in a delayed primary response, whereas memory CD8 T cells generated in CD28-deficient mice appeared almost normal in terms of both phenotype and effector cytokine profile, but they exhibited a significantly reduced proliferative capacity upon secondary challenge while retaining immediate in vivo effector capabilities: in vivo cytotoxicity and short-term in vivo protective capacity. Overall, our data point to an absolute requirement for professional APCs and the expression of the costimulatory molecules CD80/86 for efficient CD8 T cell priming by adenoviral vectors. Additionally, our results suggest the existence of an alternative receptor for CD80/86, which may substitute, in part, for CD28.