Background: Previous Costa Rica Vaccine Trial (CVT) reports separately demonstrated vaccine efficacy against HPV16 and HPV18 (HPV16/18) infections at the cervical, anal, and oral regions; however, the combined overall multisite efficacy (protection at all three sites) and vaccine efficacy among women infected with HPV16 or HPV18 prior to vaccination are less known. Methods: Women age 18 to 25 years from the CVT were randomly assigned to the HPV16/18 vaccine (Cervarix) or a hepatitis A vaccine. Cervical, oral, and anal specimens were collected at the four-year follow-up visit from 4186 women. Multisite and single-site vaccine efficacies (VEs) and 95% confidence intervals (CIs) were computed for one-time detection of point prevalent HPV16/18 in the cervical, anal, and oral regions four years after vaccination. All statistical tests were two-sided. Results: The multisite woman-level vaccine efficacy was highest among “naïve” women (HPV16/18 seronegative and cervical HPV high-risk DNA negative at vaccination) (vaccine efficacy = 83.5%, 95% CI = 72.1% to 90.8%). Multisite woman-level vaccine efficacy was also demonstrated among women with evidence of a pre-enrollment HPV16 or HPV18 infection (seropositive for HPV16 and/or HPV18 but cervical HPV16/18 DNA negative at vaccination) (vaccine efficacy = 57.8%, 95% CI = 34.4% to 73.4%), but not in those with cervical HPV16 and/or HPV18 DNA at vaccination (anal/oral HPV16/18 VE = 25.3%, 95% CI = -40.4% to 61.1%). Concordant HPV16/18 infections at two or three sites were also less common in HPV16/18-infected women in the HPV vaccine vs control arm (7.4% vs 30.4%, P < .001). Conclusions: This study found high multisite vaccine efficacy among “naïve” women and also suggests the vaccine may provide protection against HPV16/18 infections at one or more anatomic sites among some women infected with these types prior to HPV16/18 vaccination.