Evidence generation partnerships between researchers and policy-makers are a potential method for producing more relevant research with greater potential to impact on policy and practice. Little is known about how such partnerships are enacted in practice, however, or how to increase their effectiveness. We aimed to determine why researchers and policy-makers choose to work together, how they work together, which partnership models are most common, and what the key (1) relationship-based and (2) practical components of successful research partnerships are. Semi-structured qualitative interviews were conducted with 18 key informants largely based in New South Wales, Australia, who were (1) researchers experienced in working in partnership with policy in health or health-related areas or (2) policy and programme developers and health system decision-makers experienced in working in partnership with researchers. Data was analysed thematically by two researchers. Researcher-initiated and policy agency-initiated evidence generation partnerships were common. While policy-initiated partnerships were thought to be the most likely to result in impact, researcher-initiated projects were considered important in advancing the science and were favoured by researchers due to greater perceived opportunities to achieve key academic career metrics. Participants acknowledged that levels of collaboration varied widely in research/policy partnerships from minimal to co-production. Co-production was considered a worthy goal by all, conferring a range of benefits, but one that was difficult to achieve in practice. Some participants asserted that the increased time and resources required for effective co-production meant it was best suited to evaluation and implementation projects where the tacit, experiential knowledge of policy-makers provided critical nuance to underpin study design, implementation and analysis. Partnerships that were mutually considered to have produced the desired outcomes were seen to be underpinned by a range of both relationship-based (such as shared aims and goals and trust) and practical factors (such as sound governance and processes). Our findings highlight the important role of policy-makers in New South Wales in ensuring the relevance of research. There is still much to understand about how to initiate and sustain successful research/policy partnerships, particularly at the highly collaborative end.