Background: Bioinformatically designed mosaic antigens increase the breadth of HIV vaccine-elicited immunity. This study compared the safety, tolerability, and immunogenicity of a newly developed, tetravalent Ad26 vaccine with the previously tested trivalent formulation. Methods: This randomised, parallel-group, placebo-controlled, double-blind, phase 1/2a study (TRAVERSE) was done at 11 centres in the USA and one centre in Rwanda. Eligible participants were adults aged 18 to 50 years, who were HIV-uninfected, healthy at screening based on their medical history and a physical examination including laboratory assessment and vital sign measurements, and at low risk of HIV infection in the opinion of study staff, who applied a uniform definition of low-risk guidelines that was aligned across sites. Enrolled participants were randomly assigned at a 2:1 ratio to tetravalent and trivalent groups. Participants in tetravalent and trivalent groups were then further randomly assigned at a 5:1 ratio to adenovirus 26 (Ad26)-vectored vaccine and placebo subgroups. Randomisation was stratified by region (USA and Rwanda) and based on a computer-generated schedule using randomly permuted blocks prepared under the sponsor's supervision. We masked participants and investigators to treatment allocation throughout the study. On day 0, participants received a first injection of tetravalent vaccine (Ad26.Mos4.HIV or placebo) or trivalent vaccine (Ad26.Mos.HIV or placebo), and those injections were repeated 12 weeks later. At week 24, vaccine groups received a third dose of tetravalent or trivalent together with clade C gp140, and this was repeated at week 48, with placebos again administered to the placebo group. All study vaccines and placebo were administered by intramuscular injection in the deltoid muscle. We assessed adverse events in all participants who received at least one study injection (full analysis set) and Env-specific binding antibodies in all participants who received at least the first three vaccinations according to the protocol-specified vaccination schedule, had at least one measured post-dose blood sample collected, and were not diagnosed with HIV during the study (per-protocol set). This study is registered with Clinicaltrials.gov, NCT02788045. Findings: Of 201 participants who were enrolled and randomly assigned, 198 received the first vaccination: 110 were in the tetravalent group, 55 in the trivalent group, and 33 in the placebo group. Overall, 185 (93%) completed two scheduled vaccinations per protocol, 180 (91%) completed three, and 164 (83%) completed four. Solicited, self-limiting local, systemic reactogenicity and unsolicited adverse events were similar in vaccine groups and higher than in placebo groups. All participants in the per-protocol set developed clade C Env binding antibodies after the second vaccination, with higher total IgG titres after the tetravalent vaccine than after the trivalent vaccine (10 413 EU/mL, 95% CI 7284–14 886 in the tetravalent group compared with 5494 EU/mL, 3759–8029 in the trivalent group). Titres further increased after the third and fourth vaccinations, persisting at least through week 72. Other immune responses were also higher with the tetravalent vaccine, including the magnitude and breadth of binding antibodies against a cross-clade panel of Env antigens, and the magnitude of IFNγ ELISPOT responses (median 521 SFU/106 peripheral blood mononuclear cells [PBMCs] in the tetravalent group and median 282 SFU/106 PBMCs in the trivalent group after the fourth vaccination) and Env-specific CD4+ T-cell response rates after the third and fourth vaccinations. No interference by pre-existing Ad26 immunity was identified. Interpretation: The tetravalent vaccine regimen was generally safe, well-tolerated, and found to elicit higher immune responses than the trivalent regimen. Regimens that use this tetravalent vaccine component are being advanced into field trials to assess efficacy against HIV-1 infection. Funding: National Institutes of Health, Henry M Jackson Foundation for Advancement of Military Medicine and the US Department of Defense, Ragon Institute of MGH, MIT, & Harvard, Bill & Melinda Gates Foundation, and Janssen Vaccines & Prevention.