Marine forests dominated by macroalgae have experienced noticeable regression along some temperate and subpolar rocky shores. Along continuously disturbed shores, where natural recovery is extremely difficult, these forests are often permanently replaced by less structured assemblages. Thus, implementation of an active restoration plan emerges as an option to ensure their conservation. To date, active transplantation of individuals from natural and healthy populations has been proposed as a prime vehicle for restoring habitat-forming species. However, given the threatened and critical conservation status of many populations, less invasive techniques are required. Some authors have experimentally explored the applicability of several non-destructive techniques based on recruitment enhancement for macroalgae restoration; however, these techniques have not been effectively applied to restore forest-forming fucoids. Here, for the first time, we successfully restored four populations of Cystoseira barbata (i.e., they established self-maintaining populations of roughly 25 m2) in areas from which they had completely disappeared at least 50 years ago using recruitment-enhancement techniques. We compared the feasibility and costs of active macroalgal restoration by means of in situ (wild-collected zygotes and recruits) and ex situ (provisioning of lab-cultured recruits) techniques. Mid/long-term monitoring of the restored and reference populations allowed us to define the best indicators of success for the different restoration phases. After 6 years, the densities and size structure distributions of the restored populations were similar and comparable to those of the natural reference populations. However, the costs of the in situ recruitment technique were considerably lower than those of the ex situ technique. The restoration method, monitoring and success indicators proposed here may have applicability for other macroalgal species, especially those that produce rapidly sinking zygotes. Recruitment enhancement should become an essential tool for preserving Cystoseira forests and their associated biodiversity.