The use of evidence has become a foundational part of health promotion practice. Although there is a general consensus that adopting an evidence-based approach is necessary for practice, disagreement remains about what types of evidence practitioners should use to guide their work. An empirical understanding of how practitioners conceptualize and use evidence has been lacking in the literature. In this article, we explore (i) practitioners’ purposes for using evidence, (ii) types of evidence they valued, and (iii) qualities that made evidence useful for practice. 58 semi-structured interviews and 250 h of participant and non-participant observation were conducted with 54 health promotion practitioners working across New South Wales, Australia. Interviews were recorded and transcribed, and field notes were written during the observations; these were analysed using Grounded Theory methods. Practitioners used evidence for practical and strategic purposes, and valued four different types of evidence according to their relevance and usefulness for these purposes. Practitioners’ ideal evidence was generated within their practice settings, and met both substantive and procedural evaluation criteria. We argue that due to the complex nature of their work, practitioners rely on a diverse range of evidence and require organizational structures that will support them in doing so.