Seaweeds are a sustainable source of novel functional ingredients with applicability in pharmaceutics, biotechnology, and food science. The bioactivity of most of these marine compounds has scarcely been studied. The present study overviews the bioactivity of the polysaccharide fucoidan derived from Fucus vesiculosus brown algae as an antimicrobial agent against Listeria monocytogenes and Salmonella enterica serovar Typhimurium. The results obtained in vitro in reference medium reveal a bacteriostatic and bactericidal effect of fucoidan against both pathogens, this bioactivity being significantly dependent (p-value ≤ 0.05) on the concentration, 5–1000 µg/mL, temperature, 8–37 ◦C, and exposure time, 0–12 days. The results were validated in the formulation of a new functional pasteurized apple beverage to be commercialized under refrigeration. Fucoidan added at 25–100 µg/mL was highly effective against both pathogens. These results increase knowledge for the future formulation of new functional beverages that include marine compounds (high content in fibre, high content in protein; prebiotic and antioxidant properties), additionally revealing antimicrobial potential.