Background: Gender-based violence (GBV) represents a major cause of psychological morbidity worldwide, and particularly in low- and middle-income countries (LMICs). Although there are effective treatments for common mental disorders associated with GBV, they typically require lengthy treatment programs that may limit scaling up in LMICs. The aim of this study was to test the effectiveness of a new 5-session behavioural treatment called Problem Management Plus (PM+) that lay community workers can be taught to deliver. Methods and findings: In this single-blind, parallel, randomised controlled trial, adult women who had experienced GBV were identified through community screening for psychological distress and impaired functioning in Nairobi, Kenya. Participants were randomly allocated in a 1:1 ratio either to PM+ delivered in the community by lay community health workers provided with 8 days of training or to facility-based enhanced usual care (EUC) provided by community nurses. Participants were aware of treatment allocation, but research assessors were blinded. The primary outcome was psychological distress as measured by the total score on the 12-item General Health Questionnaire (GHQ-12) assessed at 3 months after treatment. Secondary outcomes were impaired functioning (measured by the WHO Disability Adjustment Schedule [WHODAS]), symptoms of posttraumatic stress (measured by the Posttraumatic Stress Disorder Checklist [PCL]), personally identified problems (measured by Psychological Outcome Profiles [PSYCHLOPS]), stressful life events (measured by the Life Events Checklist [LEC]), and health service utilisation. Between 15 April 2015 and 20 August 2015, 1,393 women were screened for eligibility on the basis of psychological distress and impaired functioning. Of these, 518 women (37%) screened positive, of whom 421 (81%) were women who had experienced GBV. Of these 421 women, 209 were assigned to PM+ and 212 to EUC. Follow-up assessments were completed on 16 January 2016. The primary analysis was intention to treat and included 53 women in PM+ (25%) and 49 women in EUC (23%) lost to follow-up. The difference between PM+ and EUC in the change from baseline to 3 months on the GHQ-12 was 3.33 (95% CI 1.86–4.79, P = 0.001) in favour of PM+. In terms of secondary outcomes, for WHODAS the difference between PM+ and EUC in the change from baseline to 3-month follow-up was 1.96 (95% CI 0.21–3.71, P = 0.03), for PCL it was 3.95 (95% CI 0.06–7.83, P = 0.05), and for PSYCHLOPS it was 2.15 (95% CI 0.98–3.32, P = 0.001), all in favour of PM+. These estimated differences correspond to moderate effect sizes in favour of PM+ for GHQ-12 score (0.57, 95% CI 0.32–0.83) and PSYCHLOPS (0.67, 95% CI 0.31–1.03), and small effect sizes for WHODAS (0.26, 95% CI 0.02–0.50) and PCL (0.21, 95% CI 0.00–0.41). Twelve adverse events were reported, all of which were suicidal risks detected during screening. No adverse events were attributable to the interventions or the trial. Limitations of the study include no long-term follow-up, reliance on self-report rather than structured interview data, and lack of an attention control condition. Conclusions: Among a community sample of women in urban Kenya with a history of GBV, a brief, lay-administered behavioural intervention, compared with EUC, resulted in moderate reductions in psychological distress at 3-month follow-up.