Background: Despite international recommendations, coverage of syphilis testing in pregnant women and treatment of those found seropositive remains limited in sub-Saharan Africa. We assessed whether combining the provision of supplies with a behavioural intervention was more effective than providing supplies only, to improve syphilis screening and treatment during antenatal care. Methods: In this 18-month, cluster randomised controlled trial, we randomly assigned (1:1) 26 urban antenatal care clinics in Kinshasa, Democratic Republic of the Congo, and Lusaka, Zambia, to receive a behavioural intervention (opinion leader selection, academic detailing visits, reminders, audits and feedback, and supportive supervision) plus supplies for syphilis testing and treatment (intervention group) or to receive supplies only (control group). The primary outcomes were proportion of pregnant women who had syphilis screening out of the total who attended the clinic; and the proportion of women who had treatment with benzathine benzylpenicillin out of those who tested positive for syphilis at their first antenatal care visit. This trial is registered at ClinicalTrials.gov, number NCT02353117. Findings: The 18-month study period was Feb 1, 2016, to July 14, 2017. 18 357 women were enrolled at the 13 intervention clinics and 17 679 women were enrolled at the 13 control clinics at their first antenatal care visit. Syphilis screening was done in a median of 99·9% (IQR 99·0–100·0) of women in the intervention clinics and 93·8% (85·0–98·9) in the control clinics (absolute difference 6·1% [95% CI 1·1–14·1]; p=0·00092). Syphilis treatment at the first visit was done in a median of 100% (IQR 99·7–100·0) of seropositive women in intervention clinics and 43·2% (2·6–83·2) of seropositive women in control clinics (absolute difference 56·8% [12·8–99·0]; p=0·0028). Interpretation: A behavioural intervention, together with the provision of supplies, can lead to more than 95% of women being screened and treated for syphilis. The sole provision of supplies is sufficient to reach such levels of screening coverage but is not sufficient to ensure high levels of treatment. Funding: Bill & Melinda Gates Foundation.