Background There is an emerging body of literature suggesting that the evidence-practice divide in health policy is complex and multi-factorial but less is known about the processes by which health policy-makers use evidence and their views about the specific features of useful evidence. This study aimed to contribute to understandings of how the most influential health policy-makers view useful evidence, in ways that help explore and question how the evidence-policy divide is understood and what research might be supported to help overcome this divide. Methods A purposeful sample of 18 national and state health agency CEOs from 9 countries was obtained. Participants were interviewed using open-ended questions that asked them to define specific features of useful evidence. The analysis involved two main approaches 1)quantitative mapping of interview transcripts using Bayesian-based computational linguistics software 2)qualitative critical discourse analysis to explore the nuances of language extracts so identified. Results The decision-making, conclusions-oriented world of policy-making is constructed separately, but not exclusively, by policy-makers from the world of research. Research is not so much devalued by them as described as too technical— yet at the same time not methodologically complex enough to engage with localised policy-making contexts. It is not that policy-makers are negative about academics or universities, it is that they struggle to find complexity-oriented methodologies for understanding their stakeholder communities and improving systems. They did not describe themselves as having a more positive role in solving this challenge than academics. Conclusions These interviews do not support simplistic definitions of policy-makers and researchers as coming from two irreconcilable worlds. They suggest that qualitative and quantitative research is valued by policy-makers but that to be policy-relevant health research may need to focus on building complexity-oriented research methods for local community health and service development. Researchers may also need to better explain and develop the policy-relevance of large statistical generalisable research designs. Policy-makers and public health researchers wanting to serve local community needs may need to be more proactive about questioning whether the dominant definitions of research quality and the research funding levers that drive university research production are appropriately inclusive of excellence in such policy-relevant research.