Simple Summary The continuous emergence of new pathogenic strains of bacteria resistant to antibiotics highlights the importance of search for the new natural sources of antimicrobial compounds. Fucoidans, sulfated polysaccharides from the cell walls of brown algae, attract the attention of many researchers due to their wide range of biological activities. Being natural and practically non-toxic, they are considered as a promising antimicrobial component that could, where possible, replace the use of strong chemical antiseptics and modern antibiotics. Natural fucoidans are polydisperse polysaccharides whose composition can vary greatly depending on the species, habitat, as well as on the way of purification. In this work, we investigate the structure and antibacterial properties of fucoidans from the brown algae Fucus vesiculosus gathered in the littoral of the Barents Sea. These fucoidans appear to have a significant bacteriostatic effect on the growth of four tested bacterial strains. Such an effect was more pronounced for crude fucoidan samples that did not undergo additional steps of purification. Abstract Fucoidans, sulfated polysaccharides found in cell walls of brown algae, are considered as a promising antimicrobial component for various applications in medicine and the food industry. In this study, we compare the antibacterial properties of two fractions of fucoidan from the brown algae Fucus vesiculosus gathered in the littoral of the Barents Sea and sampled at different stages of purification. The crude fraction of fucoidan was isolated from algae by extraction with aqueous ethanol and sonication. The purified fraction was obtained by additional treatment of the crude fraction with a solution of calcium chloride. The structural features of both fractions were characterized in detail and their antibacterial effects against several Gram-positive and Gram-negative bacteria were compared by photometry, acridine orange staining assay, and atomic force microscopy. Fucoidan inhibited growth in all of the above microorganisms, showing a bacteriostatic effect with minimum inhibitory concentrations (MIC) in the range between 4 and 6 mg/mL, with E. coli being the most sensitive to both fractions. Changes in the chemical composition after treatment of the crude fraction with a solution of calcium chloride led to a decrease in the content of sulfates and uronic acids and diminished antibacterial activity.