A critical goal of vaccine development for a wide variety of pathogens is the induction of potent and durable mucosal immunity. However, it has been assumed that this goal would be difficult to achieve by systemic vaccination due to the anatomic and functional distinctness of the systemic and mucosal immune systems and the resultant compartmentalization of immune responses. In this study, we show that Ag-specific CD8+ T lymphocytes traffic efficiently to mucosal surfaces following systemic vaccination. Intramuscular immunization with recombinant adenovirus (rAd) vector-based vaccines expressing SIV Gag resulted in potent, durable, and functional CD8+ T lymphocyte responses at multiple mucosal effector sites in both mice and rhesus monkeys. In adoptive transfer studies in mice, vaccine-elicited systemic CD8+ T lymphocytes exhibited phenotypic plasticity, up-regulated mucosal homing integrins and chemokine receptors, and trafficked rapidly to mucosal surfaces. Moreover, the migration of systemic CD8+ T lymphocytes to mucosal compartments accounted for the vast majority of Ag-specific mucosal CD8+ T lymphocytes induced by systemic vaccination. Thus, im vaccination can overcome immune compartmentalization and generate robust mucosal CD8+ T lymphocyte memory. These data demonstrate that the systemic and mucosal immune systems are highly coordinated following vaccination.