Defining the correlates of immune protection conferred by SIVnef, the most effective vaccine against SIV challenge, could enable the design of a protective vaccine against HIV infection. Here we provide a comprehensive assessment of immune responses that protect against SIV infection through detailed analyses of cellular and humoral immune responses in the blood and tissues of rhesus macaques vaccinated with SIVnef and then vaginally challenged with wild-type SIV. Despite the presence of robust cellular immune responses, animals at 5 weeks after vaccination displayed only transient viral suppression of challenge virus, whereas all macaques challenged at weeks 20 and 40 post-SIVnef vaccination were protected, as defined by either apparent sterile protection or significant suppression of viremia in infected animals. Multiple parameters of CD8 T cell function temporally correlated with maturation of protection, including polyfunctionality, phenotypic differentiation, and redistribution to gut and lymphoid tissues. Importantly, we also demonstrate the induction of a tissue-resident memory population of SIV-specific CD8 T cells in the vaginal mucosa, which was dependent on ongoing low-level antigenic stimulation. Moreover, we show that vaginal and serum antibody titers inversely correlated with post-challenge peak viral load, and we correlate the accumulation and affinity maturation of the antibody response to the duration of the vaccination period as well as to the SIVnef antigenic load. In conclusion, maturation of SIVnef-induced CD8 T cell and antibody responses, both propelled by viral persistence in the gut mucosa and secondary lymphoid tissues, results in protective immune responses that are able to interrupt viral transmission at mucosal portals of entry as well as potential sites of viral dissemination.