The antiviral activity of different structure fucoidans (α-l-fucans and galactofucans) was studied using two model viral systems based on a lentiviral vectors and a replication competent Moloney murine leukemia virus (Mo-MuLV). It was found that investigated fucoidans have no cytotoxic effects on Jurkat and SC-1cell at the concentration range of 0.001–100 µg/mL. Fucoidans with different efficiency suppressed transduction of Jurkat cell line by pseudo-HIV-1 particles carrying the envelope protein of HIV-1 and infection of SC-1 cells by Mo-MuLV. According to our data, all natural fucoidans can be considered as potential anti-HIV agents regardless of their carbohydrate backbone and degree of sulfating, since their activity is shown at low concentrations (0.001–0.05 µg/mL). High molecular weight fucoidans isolated from Saccharina cichorioides (1.3-α-l-fucan), and S. japonica (galactofucan) were the most effective inhibitors.