An efficacious human immunodeficiency virus (HIV) vaccine will likely require induction of both mucosal and systemic immune responses. We compared the immunogenicity and protective efficacy of two mucosal/systemic vaccine regimens and investigated their effects on the rectal microbiome. Rhesus macaques were primed twice mucosally with replication-competent adenovirus type 5 host range mutant (Ad5hr)-simian immunodeficiency virus (SIV) recombinants and boosted twice intramuscularly with ALVAC-SIV recombinant plus SIV gp120 protein or with DNA for SIV genes and rhesus interleukin-12 plus SIV gp120 protein. Controls received empty Ad5hr vector and alum adjuvant only. Both regimens elicited strong, comparable mucosal and systemic cellular and humoral immunity. Prevaccination rectal microbiomes of males and females differed and significantly changed over the course of immunization, most strongly in females after Ad5hr immunizations. Following repeated low-dose intrarectal SIV challenges, both vaccine groups exhibited modestly but significantly reduced acute viremia. Male and female controls exhibited similar acute viral loads; however, vaccinated females, but not males, exhibited lower levels of acute viremia, compared to same-sex controls. Few differences in adaptive immune responses were observed between the sexes. Striking differences in correlations of the rectal microbiome of males and females with acute viremia and immune responses associated with protection were seen and point to effects of the microbiome on vaccine-induced immunity and viremia control. Our study clearly demonstrates direct effects of a mucosal SIV vaccine regimen on the rectal microbiome and validates our previously reported SIV vaccine-induced sex bias. Sex and the microbiome are critical factors that should not be overlooked in vaccine design and evaluation. IMPORTANCE Differences in HIV pathogenesis between males and females, including immunity postinfection, have been well documented, as have steroid hormone effects on the microbiome, which is known to influence mucosal immune responses. Few studies have applied this knowledge to vaccine trials. We investigated two SIV vaccine regimens combining mucosal priming immunizations and systemic protein boosting. We again report a vaccine-induced sex bias, with female rhesus macaques but not males displaying significantly reduced acute viremia. The vaccine regimens, especially the mucosal primes, significantly altered the rectal microbiome. The greatest effects were in females. Striking differences between female and male macaques in correlations of prevalent rectal bacteria with viral loads and potentially protective immune responses were observed. Effects of the microbiome on vaccine-induced immunity and viremia control require further study by microbiome transfer. However, the findings presented highlight the critical importance of considering effects of sex and the microbiome in vaccine design and evaluation.