A safe, efficacious vaccine is required to stop the AIDS pandemic. Disappointing results from the STEP trial implied a need to include humoral anti-HIV-1 responses, a notion supported by RV144 trial data even though correlates of protection are unknown. We vaccinated rhesus macaques with recombinant simian immunodeficiency virus (SIV) Gag-Pol particles, HIV-1 Tat and trimeric clade C (HIV-C) gp160, which induced cross-neutralizing antibodies (nAbs) and robust cellular immune responses. After five low-dose mucosal challenges with a simian-human immunodeficiency virus (SHIV) that encoded a heterologous R5 HIV-C envelope (22.1% divergence from the gp160 immunogen), 94% of controls became viremic, whereas one third of vaccinees remained virus-free. Upon high-dose SHIV rechallenge, all controls became infected, whereas some vaccinees remained aviremic. Peak viremia was inversely correlated with both cellular immunity (p<0.001) and cross-nAb titers (p<0.001). These data simultaneously linked cellular as well as humoral immune responses with the degree of protection for the first time.