We examine the perspectives of health promotion practitioners on their approaches to determining health promotion practice, in particular on the role of research and relationships in this process. Using Grounded Theory methods, we analysed 58 semi-structured interviews with 54 health promotion practitioners in New South Wales, Australia. Practitioners differentiated between relationship-based and research-based approaches as two sources of knowledge to guide health promotion practice. We identify several tensions in seeking to combine these approaches in practice and describe the strategies that participants adopted to manage these tensions. The strategies included working in an evidence-informed rather than evidence-based way, creating new evidence about relationship-based processes and outcomes, adopting 'relationship-based' research and evaluation methods, making research and evaluation useful for communities, building research and evaluation skills and improving collaboration between research and evaluation and programme implementation staff. We conclude by highlighting three systemic factors which could further support the integration of research-based and relationship-based health promotion practices: (i) expanding conceptions of health promotion evidence, (ii) developing 'relationship-based' research methods that enable practitioners to measure complex social processes and outcomes and to facilitate community participation and benefit, and (iii) developing organizational capacity.