This manuscript is an outcome of the workshop entitled "Scientific Strategy for a Global Approach to Promote Regional Ecosystem-based Approach to Fisheries (EAF) in the Mediterranean and Black Seas" held in SSte (France) in July 2012. The workshop was organized by Work-Package 6 of the coordination action "Coordinating Research in Support to Application of Ecosystem Approach to Fisheries and Management Advice in the Mediterranean and Black Seas" (CREAM), funded by the EU Seventh Framework Programme. The main aim of the workshop was to discuss what is needed to advance on a robust scientific strategy to promote EAF in the Mediterranean and Black Seas. Participants discussed a series of scientific recommendations for promoting the coordination of initiatives with the aim of contributing to an operational EAF. Discussion was carried out on (i) what can be learnt from case studies that promote EAF worldwide, (ii) how a scientific strategy for EAF can be built, and (iii) which are the future scientific networking activities to promote EAF. Here we summarize the discussions and conclusions of the workshop, and we present the recommendations and future initiatives proposed to advance EAF in the Mediterranean and Black Seas region. Participants to the workshop agreed that the achievement of a common vision regarding the Mediterranean and Black Seas region should be one of the first and most important elements towards a successful EAF. A common vision should recognise the need to promote the reconciliation of conservation and exploitation, and to aim for a good socioeconomic and ecological status. The vision should also promote the recovery of ecosystems and rebuilding of marine commercial stocks and predator species. EAF initiatives, carried out worldwide, illustrated that whilst the development of relevant science is essential to render the EAF process operational, the involvement of stakeholders is the key factor that characterises successful initiatives. This is especially important in the Mediterranean and Black Sea context, where many stakeholders show conflicting interests and associated trade-offs. During the workshop, it became clear that numerous overlapping and poorly coordinated initiatives for EAF exist in the region. The group discussed the integration of the existing initiatives in a coordinated manner and arrived to the conclusion that a scientific network to promote coordinated and operational EAF initiatives created by the scientific community is needed. Ultimately, the discussion was focused on how to build such a scientific network and how to proceed to consolidate the regional scientific vision, with a clear scientific strategy and roadmap, including a diversified toolbox. In the short term, the proposed EAF scientific network should (i) document and coordinate scientific initiatives, (ii) promote the sharing of scientific information and capabilities, (iii) promote data availability, integration, harmonization, and interoperability, (iv) promote training capabilities and capacity building of the scientific community and stakeholders, (v) establish mechanisms to disseminate knowledge, and communicate EAF benefits, and (vi) promote concrete regional scientific initiatives. In the long run, the network should promote scientific advice on EAF to inform adaptive management, and promote EAF implementation at different geographical scales (from local to regional) using a transversal approach.