This article focuses on the dioxin problem of Baltic herring and salmon fisheries and its governance that is based on natural scientific knowledge. The dioxin problem weakens the perceived quality of Baltic salmon and herring as food and affects the way the catches can be used. This influences negatively the fishing livelihood, the coastal culture, and the availability of the fish for consumers. We explored how the governance of the dioxin problem could be improved, to better address its socio-economic and cultural implications. We identified four main actions: (1) adopt environmental, economic and social sustainability, and food security and safety as shared principles between the environmental, food safety/public health, and fisheries policies, (2) establish collaboration between the environmental, public health, and fisheries sectors at the regional level, (3) enhance interaction around the dioxin problem within the fisheries sector, and (4) support the participation of the Baltic fisheries stakeholders in the EU-level food safety governance. Viewing dioxins in fish not only as a natural scientific problem but as a multidimensional one would enable a wider toolbox of governing instruments to be developed to better address the different dimensions. This would support steps towards collaborative governance and a food system approach.