Brown algae Fucus virsoides and Cystoseira barbata are an abundant source of sulfated polysaccharide fucoidan, which has shown a wide range of biological activities. These activities are significantly dependent on the fucoidan chemical composition, which is closely linked with the applied extraction technique and process parameters. In order to overcome the drawbacks of lengthy conventional extraction (CE), advanced extraction techniques, such as ultrasound-assisted extraction (UAE) and non-thermal plasma (NTP), were applied. Furthermore, this study also investigated the efficiency of different solvents as well as UAE and NTP as 5 min pre-treatments prior to CE as a more effective course of cell wall breakage and, consequently, a higher polysaccharide yield (%PS). Apart from %PS, the effect of this procedure on the chemical composition and antioxidant capacity of the extracted polysaccharides was also monitored. When comparing the extraction solvent, the application of 0.1 M H2SO4, instead of H2O, resulted in a three-fold higher %PS, a higher sulfate group, and a lower fucose content. Application of CE resulted in higher %PS, uronic acids, and fucose content as well as oxygen radical absorbance capacity (ORAC) and DPPH values, while the average molecular weight (Mw), sulfate group, and glucose content were lower during CE when compared to 30 min of UAE and NTP treatment. Application of UAE and NTP as 5 min pre-treatments decreased fucose content, while %PS and sulfate content were similar to values obtained when using CE.