Food insecurity persists in many parts of Africa and Asia, despite ongoing agricultural research for development (AR4D) interventions. This is resulting in a growing demand for alternative approaches to designing and evaluating interventions in complex systems. Theory of Change (ToC) is an approach which may be useful because it enables stakeholders to present and test their theories and assumptions about why and how impact may occur, ideally within an environment conducive to iterative reflection and learning. However, ToC is yet to be appropriately mainstreamed into development by donors, researchers and practitioners. We carried out a literature review, triangulated by interviews with 26 experts in African and Asian food security, consisting of researchers, advisors to programs, and donors. Although 17 (65%) of the experts had adopted ToC, their responses and the literature revealed four challenges to mainstreaming: (i) different interpretations of ToC; (ii) incoherence in relationships among the constituent concepts of ToC; (iii) confused relationships between ToC and project "logframes"; and (iv) limitations in necessary skills and commitment for enacting ToC. A case study of the evolution of a ToC in a West African AR4D project over 4 years which exemplified these challenges is presented. Five recommendations arise to assist the mainstreaming of ToC: (i) select a type of ToC suited to the relative complexity of the problem and focal system of interest; (ii) state a theory or hypotheses to be tested as the intervention progresses; (iii) articulate the relationship between the ToC and parallel approaches (e.g. logframe); (iv) accept that a ToC is a process, and (v) allow time and resources for implementers and researchers to develop ToC thinking within projects. Finally, we suggest that communities of practice should be established among AR4D and donor organisations to test, evaluate and improve the contribution that ToCs can make to sustainable food security and agricultural development.