Eutrophication is a phenomenon which can rapidly generate masses of marine macroalgae, particularly in areas with high nutrient pollution. Washed ashore, this biomass impairs coastal tourism and negatively affects the coastal ecosystem. The present study evaluates the biochemical methane potential (BMP) of a macroalgae mix (Rügen-Mix, RM (RM = Rügen-Mix)) originating from Rügen, Germany. To improve biomethane recovery, thermo-acidic pretreatment was applied to the biomass prior to biomethanation to disintegrate the biomass macrostructure. Acid hydrolysis was successfully triggered with 0.2 M industry-grade HCl at 80 °C for a 2 h period, increasing biomethane recovery by +39%, with a maximum BMP of 121 mL·g−1 volatile solids (VS). To reduce the necessity for input material, HCl was replaced by the acidic waste product flue gas condensate (FGC). Improved performance was achieved by showing an increase in biomethane recovery of +24% and a maximum BMP of 108 mL·g−1 VS. Continuous anaerobic digestion trials of RM were conducted for three hydraulic retention times, showing the feasibility of monodigestion. The biomethane recovery was 60 mL and 65 mL·g−1 VS·d−1 for thermophilic and mesophilic operation, respectively. The quality of biomethanation performance aligned to the composition of the source material which exhibited a low carbon/nitrogen ratio and an increased concentration of sulfur compounds.