Theories of change (ToCs) describe how interventions can bring about long-term outcomes through a logical sequence of intermediate outcomes and have been used to design and measure the impact of public health programmes in several countries. In recognition of their capacity to provide a framework for monitoring and evaluation, they are being increasingly employed in the development sector. The construction of a ToC typically occurs through a consultative process, requiring stakeholders to reflect on how their programmes can bring about change. ToCs help make explicit any underlying assumptions, acknowledge the role of context and provide evidence to justify the chain of causal pathways. However, while much literature exists on how to develop a ToC with respect to interventions in theory, there is comparatively little reflection on applying it in practice to complex interventions in the health sector. This paper describes the initial process of developing a ToC to inform the design of an evaluation of a complex intervention aiming to improve government payments to health workers in the Democratic Republic of Congo. Lessons learnt include: the need for the ToC to understand how the intervention produces effects on the wider system and having broad stakeholder engagement at the outset to maximise chances of the intervention's success and ensure ownership. Power relationships between stakeholders may also affect the ToC discourse but can be minimised by having an independent facilitator. We hope these insights are of use to other global public health practitioners using this approach to evaluate complex interventions.