Background: We coordinated community health worker (CHW) promotions with training and support of government clinic nurses to increase uptake of long-acting reversible contraception (LARC), specifically the copper intrauterine device (IUD) and the hormonal implant, in Kigali, Rwanda. Methods: From August 2015 to September 2016, CHW provided fertility goal-based family planning counseling focused on LARC methods, engaged couples in family planning counseling, and provided written referrals to clients expressing interest in LARC methods. Simultaneously, we provided didactic and practical training to clinic nurses on LARC insertion and removal. We evaluated: 1) aggregate pre- versus post-implementation LARC uptake as a function of CHW promotions, and 2) demographic factors associated with LARC uptake among women responding to CHW referrals. Results: 7712 referrals were delivered by 184 CHW affiliated with eight government clinics resulting in 6072 family planning clinic visits (79% referral uptake). 95% of clinic visits resulted in LARC uptake (16% copper IUD, 79% hormonal implant). The monthly average for IUD insertions doubled from 29 prior to service implementation to 61 after (p < 0.0001), and the monthly average for implant insertions increased from 109 to 309 (p < 0.0001). In adjusted analyses, LARC uptake was associated (p < 0.05) with the CHW referral being issued to the couple (versus the woman alone, adjusted odds ratio, aOR = 2.6), having more children (aOR = 1.3), desiring more children (aOR = 0.8), and having a religious affiliation (aOR = 2.9 Protestant, aOR = 3.1 Catholic, aOR = 2.5 Muslim each versus none/other). Implant versus non-LARC uptake was associated with having little or no education; meanwhile, having higher education was associated with IUD versus implant uptake. Conclusions: Fertility goal-based and couple-focused family planning counseling delivered by CHW, coupled with LARC training and support of nursing staff, substantially increased uptake of LARC methods.