Background: Observational data and non-human primate challenge studies suggest that cell-mediated immune responses might provide control of HIV replication. The Step Study directly assessed the efficacy of a cell-mediated immunity vaccine to protect against HIV-1 infection or change in early plasma HIV-1 levels. Methods: We undertook a double-blind, phase II, test-of-concept study at 34 sites in North America, the Caribbean, South America, and Australia. We randomly assigned 3000 HIV-1-seronegative participants by computer-generated assignments to receive three injections of MRKAd5 HIV-1 gag/pol/nef vaccine (n=1494) or placebo (n=1506). Randomisation was prestratified by sex, adenovirus type 5 (Ad5) antibody titre at baseline, and study site. Primary objective was a reduction in HIV-1 acquisition rates (tested every 6 months) or a decrease in HIV-1 viral-load setpoint (early plasma HIV-1 RNA measured 3 months after HIV-1 diagnosis). Analyses were per protocol and modified intention to treat. The study was stopped early because it unexpectedly met the prespecified futility boundaries at the first interim analysis. This study is registered with ClinicalTrials.gov, number NCT00095576. Findings: In a prespecified interim analysis in participants with baseline Ad5 antibody titre 200 or less, 24 (3%) of 741 vaccine recipients became HIV-1 infected versus 21 (3%) of 762 placebo recipients (hazard ratio [HR] 1·2 [95% CI 0·6-2·2]). All but one infection occurred in men. The corresponding geometric mean plasma HIV-1 RNA was comparable in infected male vaccine and placebo recipients (4·61 vs 4·41 log10 copies per mL, one tailed p value for potential benefit 0·66). The vaccine elicited interferon-γ ELISPOT responses in 75% (267) of the 25% random sample of all vaccine recipients (including both low and high Ad5 antibody titres) on whose specimens this testing was done (n=354). In exploratory analyses of all study volunteers, irrespective of baseline Ad5 antibody titre, the HR of HIV-1 infection between vaccine and placebo recipients was higher in Ad5 seropositive men (HR 2·3 [95% CI 1·2-4·3]) and uncircumcised men (3·8 [1·5-9·3]), but was not increased in Ad5 seronegative (1·0 [0·5-1·9]) or circumcised (1·0 [0·6-1·7]) men. Interpretation: This cell-mediated immunity vaccine did not prevent HIV-1 infection or reduce early viral level. Mechanisms for insufficient efficacy of the vaccine and the increased HIV-1 infection rates in subgroups of vaccine recipients are being explored. Funding: Merck Research Laboratories; the Division of AIDS, National Institute of Allergy and Infectious Diseases, in the US National Institutes of Health (NIH); and the NIH-sponsored HIV Vaccine Trials Network (HVTN). © 2008 Elsevier Ltd. All rights reserved.