Despite the advantages ensuing from preferential market access agreements, trade exchanges between Southern Mediterranean Countries (SMCs) and the EU are often hindered by food safety issues. These are particularly relevant for fruit and vegetables, which are subject to heterogeneous regulations in SMCs. This paper seeks to outline governance solutions to improve ex-ante compliance capacity of SMCs production and to enhance integration with the EU market. A set of research hypotheses, concerning the difficulties and benefits related with food safety compliance, are formulated. These hypotheses are then discussed in the light of the empirical evidence gathered from (i) public bodies involved in food safety enforcement and (ii) a direct survey conducted on 37 stakeholders in the fruit and vegetable supply chain in Italy. The main problems identified relate to the scarce harmonization among control systems in EU Member States and insufficient checks in exporting countries. The main benefits include the reduction of sanitary risk and the reinforcement of long-term trust-based relations along the supply chain. The most promising strategies encompass the improvement of inspections on production sites and of infrastructures in the countries of origin. Further areas of intervention concern the harmonization of food safety regulation between EU countries and SMCs and the development of bilateral cooperation and technical training programs.