BACKGROUND: The importance of complexity in health care policy-making and interventions, as well as research and evaluation is now widely acknowledged, but conceptual confusion reigns and few applications of complexity concepts in research design have been published. Taking user fee exemption policies as an entry point, we explore the methodological consequences of 'complexity' for health policy research and evaluation. We first discuss the difference between simple, complicated and complex and introduce key concepts of complex adaptive systems theory. We then apply these to fee exemption policies. DESIGN: We describe how the FEMHealth research project attempts to address the challenges of complexity in its evaluation of fee exemption policies for maternal care. We present how the development of a programme theory for fee exemption policies was used to structure the overall design. This allowed for structured discussions on the hypotheses held by the researchers and helped to structure, integrate and monitor the sub-studies. We then show how the choice of data collection methods and tools for each sub-study was informed by the overall design. DISCUSSION: Applying key concepts from complexity theory proved useful in broadening our view on fee exemption policies and in developing the overall research design. However, we encountered a number of challenges, including maintaining adaptiveness of the design during the evaluation, and ensuring cohesion in the disciplinary diversity of the research teams. Whether the programme theory can fulfil its claimed potential to help making sense of the findings is yet to be tested. Experience from other studies allows for some moderate optimism. However, the biggest challenge complexity throws at health system researchers may be to deal with the unknown unknowns and the consequence that complex issues can only be understood in retrospect. From a complexity theory point of view, only plausible explanations can be developed, not predictive theories. Yet here, theory-driven approaches may help.