Danish dietary guidelines recommend the Danish population to increase the consumption of fish while decreasing the consumption of red and processed meat to prevent nutrition-related diseases. However, the presence of contaminants in these foods may affect the overall risk-benefit balance of such substitution. We performed a quantitative risk-benefit assessment on substituting red and processed meat with fish in a Danish diet. We modeled the substitution among Danish adults based on data from a Danish dietary survey and compared four alternative scenarios based on varying chemical and nutrient exposures to the current consumption. We quantified the overall health impact of the substitutions in terms of Disability-Adjusted Life Years (DALYs). Approximately 150 DALYs/100,000 individuals could be averted each year if Danish adults consumed 350 g of fish/week (fatty or mix of fatty and lean) while decreasing the consumption of red and processed meat. A lower beneficial impact was observed when consumption of fish was restricted to lean fish (80 DALYs/100,000 averted), and a marked health loss (180 DALYs/100,000) was estimated when consumption was restricted to tuna. Our results show an overall beneficial effect of the substitution if the consumption of large predatory fish is low and at least half is fatty fish.