Brown macroalgae within the genus Cystoseira are some of the most relevant “ecosystem-engineers” found throughout the Mediterranean and the adjacent Atlantic coasts. Cystoseira-dominated assemblages are sensitive to anthropogenic pressures, and historical declines have been reported from some regions. In particular, Cystoseira abies-marina, thriving on shallow rocky shores, is a key species for the ecosystems of the Canary Islands. In this work, we analyse changes in the distribution and extension of C. abies-marina in the last decades on the island of Gran Canaria. This alga dominated the shallow rocky shores of the entire island in the 1980s; a continuous belt extended along 120.5 km of the coastline and occupied 928 ha. In the first decade of the 21st century, fragmented populations were found along 52.2 km of the coastline and occupied 12.6 ha. Today, this species is found along 37.8 km of the coastline and occupies only 7.4 ha, mainly as scattered patches. This regression has been drastic around the whole island, even in areas with low anthropogenic pressure; the magnitude of the decline over time and the intensity of local human impacts have not shown a significant correlation. This study highlights a real need to implement conservation and restoration policies for C. abies-marina in this region.