Background: Delivery of PrEP to adolescent girls and young women (AGYW) and to pregnant women through maternal and child health (MCH) and family planning (FP) clinics is scaling up in Kenya. Evaluation of implementation challenges and strategies is critical to optimize delivery. Methods: We conducted focus group discussions (FGDs) with healthcare workers (HCWs) in MCH and FP clinics offering PrEP in a large implementation project in Kisumu, Kenya. Discussion guides were based on the Consolidated Framework for Implementation Research (CFIR). FGDs were audio recorded and transcribed. Directed content analysis was used to identify implementation challenges and strategies to overcome them. Results: Fifty HCWs from 26 facilities participated in 8 FGDs. HCWs believed PrEP integration was appropriate because it met the needs of AGYW and pregnant women by providing a female-controlled prevention strategy and aligned with policy priorities of elimination of vertical HIV transmission. They were universally accepting of PrEP provision, especially through MCH clinics, noting the relative advantage of this approach because it: (1) enabled high coverage, (2) harmonized PrEP and MCH visits, and (3) minimized stigma compared to PrEP offered through HIV care clinics. However, HCWs noted implementation challenges affecting feasibility and adoption including: (1) increased workload and documentation burden amid workforce shortages, (2) insufficient health care worker knowledge (3) multiple implementing partners with competing priorities (4) drug and documentation form stockouts. HCWs employed various implementation strategies to overcome challenges, including task shifting from nurses to HIV testing providers, patient flow modifications (e.g., fast-tracking PrEP clients to reduce wait times), PrEP demand generation and myth clarification during health talks, provider education, dedicated PrEP delivery rooms, and coordination with adolescent-friendly services. Additional suggested strategies to improve PrEP integration included community education to increase broader PrEP awareness and enable shorter counseling sessions, and task-shifting data entry and client risk assessments. Conclusions: HCWs were enthusiastic about the appropriateness and acceptability of integrating PrEP services into MCH and FP clinics but noted challenges to adoption and feasibility. Strategies to address challenges focused on improving provider time and space constraints, and increasing provider and client knowledge.