In the present work, the phlorotannin composition of different Sargassum muticum samples collected at different locations along the North Atlantic coasts as well as the bioactivities related to these components were investigated. After pressurized liquid extraction, the samples collected at the extreme locations of a latitudinal gradient from Portugal and Norway, were found to be the richest on total phenols and, particularly, on phlorotannins, containing up to 148.97 and 5.12 mg phloroglucinol equivalents g−1, respectively. The extracts obtained from these locations were further purified and chemically characterized using a modified HILIC × RP-DAD-MS/MS method. The application of this methodology allowed the tentative identification of a great variability of phlorotannins with different degrees of polymerization (from 3 to 11) and structures, determined for the first time in S. muticum. The most-abundant phlorotannins on these samples were fuhalols, hydroxyfuhalols and phlorethols, showing also particularities and important differences depending on the geographical location. Afterwards, the antiproliferative activity of these extracts against HT-29 adenocarcinoma colon cancer cells was studied. Results revealed that the richest S. muticum samples in terms of total phlorotannins, i.e., those from Norway, presented the highest activity, showing a good cytotoxic potential at concentrations in the medium micromolar range.