Objectives: Providing a robust scientific background for the focus on gender-sensitive public health and a systematic approach to its implementation. Methods: Within the FP7-EUGenMed project (http://eugenmed.eu) a workshop on sex and gender in public health was convened on February 2-3, 2015. The experts participated in moderated discussion rounds to (1) assemble available knowledge and (2) identify structural influences on practice implementation. The findings were summarized and analyzed in iterative rounds to define overarching strategies and principles. Results: The participants discussed the rationale for implementing gender-sensitive public health and identified priorities and key stakeholders to engage in the process. Communication strategies and specific promotion strategies with distinct stakeholders were defined. A comprehensive list of gender-sensitive practices was established using the recently published taxonomy of the Expert Recommendations for Implementing Change (ERIC) project as a blueprint. Conclusions: A clearly defined implementation strategy should be mandated for all new projects in the field of gender-sensitive public health. Our tool can support researchers and practitioners with the analysis of current and past research as well as with the planning of new projects.