Leadership and management skills are critical for health programs to deliver high-quality interventions in complex systems. In malaria-eliminating countries, national and subnational health teams are reorienting strategies to address focal transmission while preventing new cases and adapting to decentralization and declines in external financing. A capacity-strengthening program in two regions in Namibia helped malaria program implementers identify and address key operational, political, and financial challenges. The program focused on developing skills and techniques in problem-solving and teamwork, engaging decision-makers, and using financial evidence to prioritize domestic resources for malaria through participatory approaches. Results of the program included an observed 40% increase in malaria case reporting, 32% increase in reporting and tracing of imported malaria cases, 10% increase in malaria case management, integration of malaria activities into local operational plans, and an increase in subnational resources for malaria teams. To promote program sustainability beyond the implementation period, key program aspects were institutionalized into existing health system structures, program staff were trained in change leadership, and participants integrated the skills and approaches into their professional roles. A capacity -strengthening program with joint focus on leadership, management, and advocacy has potential for application to other health issues and geographies.