BACKGROUND: New forms of leadership are required to bring about the fundamental health system changes demanded by primary health care (PHC). Using theory about complex adaptive systems and policy implementation, this paper considers how actors' sensemaking and the exercise of discretionary power currently combine to challenge PHC re-orientation in the South African health system; and provides examples of leadership practices that promote sensemaking and power use in support of PHC. METHODS: The paper draws on observational, interview, and reflective data collected as part of the District Innovation and Action Learning for Health Systems Development (DIALHS) project being implemented in Cape Town, South Africa. Undertaken collaboratively between health managers and researchers, the project is implemented through cycles of action-learning, including systematic reflection and synthesis. It includes a particular focus on how local health managers can better support front line facility managers in strengthening PHC. RESULTS: The results illuminate how the collective understandings of staff working at the primary level - of their working environment and changes within it - act as a barrier to centrally-led initiatives to strengthen PHC. Staff often fail to take ownership of such initiatives and experience them as disempowering. Local area managers, located between the centre and the service frontline, have a vital role to play in providing a leadership of sensemaking to mediate these challenges. Founded on personal values, such leadership entails, for example, efforts to nurture PHC-aligned values and mind-sets among staff; build relationships and support the development of shared meanings about change; instil a culture of collective inquiry and mutual accountability; and role-model management practices, including using language to signal meaning. CONCLUSIONS: PHC will only become a lived reality within the South African health system when frontline staff are able to make sense of policy intentions and incorporate them into their everyday routines and practices. This requires a leadership of sensemaking that enables front line staff to exercise their collective discretionary power in strengthening PHC. We hope this theoretically-framed analysis of one set of experiences stimulates wider thinking about the leadership needed to sustain primary health care in other settings.