Sargassum muticum (SM) is an invasive macroalgal species seasonally occurring in large quantities. While generally suitable for anaerobic digestion, recent studies resulted in low specific methane yields (SMYs), presumably due to salt, polyphenol, and high fiber contents of this marine biomass. In this study, the specific biogas yield (SBY) and SMY of SM alone as well as in co-digestion with wheat straw (WS) were investigated in batch tests at process temperatures of 44 ± 1.4 °C with a retention time of approx. 40 d. The pretreatment variants of SM were examined with regard to desalination and disintegration to potentially improve digestibility and to enhance the overall performance in anaerobic digestion. A sole mechanical treatment (pressing) and a thermo-mechanical treatment (heating and pressing) were tested. Batch assays showed that pressing increased the SMY by 15.1% whereas heating and pressing decreased the SMY by 15.7% compared to the untreated variant (87.64 ± 8.72 mL/g_VS). Both anaerobic digestion experiments generally showed that co-digestion with WS can be recommended for SM, but the observed SBY and SMY were still similar to those of other studies in which SM was not pretreated. The mechanical pretreatment of SM, however, offers the potential to enhance the SMY in the anaerobic digestion of SM with WS, but further research is necessary to identify the optimum upgrading approaches since the overall SMY of SM is relatively low compared to other substrates that are commonly used in anaerobic digestion. In addition to anaerobic digestion, SM as an already available biomass could also be of interest for further utilization approaches such as fiber production.