The influence of preexisting immunity to viral vectors is a major issue for the development of viral-vectored vaccines. In this study, we investigate the effect of preexisting vaccinia virus immunity on the immunogenicity and efficacy of a DNA/modified vaccinia Ankara (MVA) SIV vaccine in rhesus macaques using a pathogenic intrarectal SIV251 challenge. Preexisting immunity decreased SIV-specific CD8 and CD4 T cell responses but preserved the SIV-specific humoral immunity. In addition, preexisting immunity did not diminish the control of an SIV challenge mediated by the DNA/MVA vaccine. The peak and set point viremia was 150- and 17-fold lower, respectively, in preimmune animals compared with those of control animals. The peak and set point viremia correlated directly with colorectal virus at 2 wk postchallenge suggesting that early control of virus replication at the site of viral challenge was critical for viral control. Factors that correlated with early colorectal viral control included 1) the presence of anti-SIV IgA in rectal secretions, 2) high-avidity binding Ab for the native form of Env, and 3) low magnitude of vaccine-elicited SIV-specific CD4 T cells displaying the CCR5 viral coreceptor. The frequency of SIV-specific CD8 T cells in blood and colorectal tissue at 2 wk postchallenge did not correlate with early colorectal viral control. These results suggest that preexisting vaccinia virus immunity may not limit the potential of recombinant MVA vaccines to elicit humoral immunity and highlight the importance of immunodeficiency virus vaccines achieving early control at the mucosal sites of challenge.