Transitioning agri-food systems towards increased sustainability and resilience requires that attention be paid to sustainable food consumption policies. Policy-making processes often require the engagement and acceptance of key stakeholders. This study analyses stakeholders’ solutions for creating sustainable agri-food systems, through interviews with a broad range of stakeholders including food value chain actors, non-governmental organizations, governmental institutions, research institutions and academic experts. The study draws on 38 in-depth, semi-structured interviews conducted in four European countries: France, Iceland, Italy and the UK, as well as three interviews with high-level EU experts. The interviewees’ solutions were analysed according to a five-category typology of policy tools, encompassing direct activity regulations, and market-based, knowledge-based, governance and strategic policy tools. Most of the identified solutions were located in the strategic tools category, reflecting shared recognition of the need to integrate food policy to achieve long-term goals. Emerging solutions—those which were most commonly identified among the different national contexts—were then used to derive empirically-grounded and more universally applicable recommendations for the advancement of sustainable food consumption policies.