The Joint United Nations Programme on HIV and AIDS proposed to reduce the vertical transmission of HIV from ∼72,200 to ∼8300 newly infected children by 2015 in South Africa (SA). However, cultural, infrastructural, and socio-economic barriers hinder the implementation of the prevention of mother-to-child transmission (PMTCT) protocol, and research on potential solutions to address these barriers in rural areas is particularly limited. This study sought to identify challenges and solutions to the implementation, uptake, and sustainability of the PMTCT protocol in rural SA. Forty-eight qualitative interviews, 12 focus groups discussions (n = 75), and one two-day workshop (n = 32 participants) were conducted with district directors, clinic leaders, staff, and patients from 12 rural clinics. The delivery and uptake of the PMTCT protocol was evaluated using the Consolidated Framework for Implementation Research (CFIR); 15 themes associated with challenges and solutions emerged. Intervention characteristics themes included PMTCT training and HIV serostatus disclosure. Outer-setting themes included facility space, health record management, and staff shortage; inner-setting themes included supply use and availability, staff–patient relationship, and transportation and scheduling. Themes related to characteristics of individuals included staff relationships, initial antenatal care visit, adherence, and culture and stigma. Implementation process themes included patient education, test results delivery, and male involvement. Significant gaps in care were identified in rural areas. Information obtained from participants using the CFIR framework provided valuable insights into solutions to barriers to PMTCT implementation. Continuously assessing and correcting PMTCT protocol implementation, uptake and sustainability appear merited to maximize HIV prevention.