While the long-term goal is to develop highly effective AIDS vaccines, first generation vaccines may be only partially effective. Other HIV prevention modalities such as preexposure prophylaxis with antiretrovirals (PrEP) may have limited efficacy as well. The combined administration of vaccine and PrEP (VAXPREP), however, may have a synergistic effect leading to an overall benefit that is greater than the sum of the individual effects. We propose two test-of-concept trial designs for an AIDS vaccine plus oral or topical ARV. In one design, evidence that PrEP reduces the risk of HIV acquisition is assumed to justify offering it to all participants. A two-arm study comparing PrEP alone to VAXPREP is proposed in which 30 to 60 incident infections are observed to assess the additional benefit of vaccination on risk of infection and setpoint viral load. The demonstrated superiority of VAXPREP does not imply vaccine alone is efficacious. Similarly, the lack of superiority does not imply vaccine alone is ineffective, as antagonism could exist between vaccine and PrEP. In the other design, PrEP is assumed not to be in general use. A 2 × 2 factorial design is proposed in which high-risk individuals are randomized to one of four arms: placebo vaccine given with placebo PrEP, placebo vaccine given with PrEP, vaccine given with placebo PrEP, or VAXPREP. Between 60 and 210 infections are required to detect a benefit of vaccination with or without PrEP on risk of HIV acquisition or setpoint viral load, with fewer infections needed when synergy is present.