The aim of this work was to evaluate the potential of ultrasound (US), alone or in combination with mild heating and/or EDTA towards reduction of As, Cd, I, and Hg content of Laminaria hyperborea. Concentrations of As, Cd, I, and Hg of 56.29, 0.596, 7340, and <0.01 mg kg−1 of dry weight, respectively, were found in L. hyperborea blades. Treatment with US at 50 ◦C increased approx. 2-fold the amount of As released, although did not affect significantly the content of Cd or I, as compared to control (no US) samples. Reducing the temperature to 8 ◦C significantly decreased the effect of US, but heating at 80 ◦C did not cause a significant effect as compared to treatments at 50 ◦C. On the other hand, treatment with 0.1 N EDTA at 50 ◦C enhanced the percentage of Cd released by approximately 7-fold, regardless of sonication. In the present work, the combination of US and EDTA at 50 ◦C for 5 min led to a significant reduction of the As (32%), Cd (52%) and I (31%) content in L. hyperborea, thus improving the product’s safety for consumers.