Background: In the Democratic Republic of Congo (DRC), men who have sex with men (MSM) and female sex workers (FSW) have the highest HIV prevalence but have the least access to services due to their marginalization within Congolese society. Methods: The Projet Intégré de VIH/SIDA au Congo (ProVIC) aims to reduce the risk and impact of HIV in the DRC through community- and facility-based prevention, counseling and testing, and treatment strategies aimed at high-risk populations, including MSM and FSW. To more effectively meet the needs of key populations, ProVIC tailored the existing interventions to better suit MSM and FSW by offering mobile counseling and rapid HIV testing services at night in MSM and FSW “hotspots,” targeting outreach to and mobilizing key populations through social networks of MSM and FSW peer educators and recruiters, and referring MSM and FSW who test HIV positive to “friendly” clinics. Results: Through these approaches, ProVIC was able to reach 2,621 MSM and 12,746 FSW with targeted prevention messaging in 2013 and provide testing and counseling services to 4,366 MSM and 21,033 FSW from October 2012 to June 2014. Conclusions: By applying innovative adaptations geared toward key populations, ProVIC has been able to better reach MSM and FSW in the DRC. ProVIC's targeted interventions for MSM and FSW provide promising examples of programming that can be used to meet the HIV prevention and testing needs of key populations and improve referrals for care and treatment, particularly in complex and unstable settings similar to the DRC.