Vaccines are largely evaluated for their ability to promote adaptive immunity, with little focus on the induction of negative immune regulators. Adjuvants facilitate and enhance vaccine-induced immune responses and have been explored for mediating protection against HIV. Using a regimen of peptide priming followed by a modified vaccinia Ankara (MVA) boost in a nonhuman primate model, we found that an SIV vaccine incorporating molecular adjuvants mediated partial protection against rectal SIVmac251 challenges. Animals treated with vaccine and multiple adjuvants exhibited a reduced viral load (VL) compared with those treated with vaccine only. Surprisingly, animals treated with adjuvant alone had reduced VLs that were comparable to or better than those of the vaccine-treated group. VL reduction was greatest in animals with the MHC class I allele Mamu-A*01 that were treated with adjuvant only and was largely dependent on CD8⁺ T cells. Early VLs correlated with Ki67⁺CCR5⁺CD4⁺ T cell frequency, while set-point VL was associated with expansion of a myeloid cell population that was phenotypically similar to myeloid-derived suppressor cells (MDSCs) and that suppressed T cell responses in vitro. MDSC expansion occurred in animals receiving vaccine and was not observed in the adjuvant-only group. Collectively, these results indicate that vaccine-induced MDSCs inhibit protective cellular immunity and suggest that preventing MDSC induction may be critical for effective AIDS vaccination.