Certain sulfated glycans, including those from marine sources, can show potential effects against SARS-CoV-2. Here, a new fucosylated chondroitin sulfate (FucCS) from the sea cucumber Pentacta pygmaea (PpFucCS) (MW ∼10–60 kDa) was isolated and structurally characterized by NMR. PpFucCS is composed of {→3)-β-GalNAcX-(1→4)-β-GlcA-[(3→1)Y]-(1→}, where X = 4S (80%), 6S (10%) or nonsulfated (10%), Y = α-Fuc2,4S (40%), α-Fuc2,4S-(1→4)-α-Fuc (30%), or α-Fuc4S (30%), and S = SO₃⁻. The anti-SARS-CoV-2 activity of PpFucCS and those of the FucCS and sulfated fucan isolated from Isostichopus badionotus (IbFucCS and IbSF) were compared with that of heparin. IC₅₀ values demonstrated the activity of the three holothurian sulfated glycans to be ∼12 times more efficient than heparin, with no cytotoxic effects. The dissociation constant (K_D) values obtained by surface plasmon resonance of the wildtype SARS-CoV-2 spike (S)-protein receptor-binding domain (RBD) and N501Y mutant RBD in interactions with the heparin-immobilized sensor chip were 94 and 1.8 × 10³ nM, respectively. Competitive surface plasmon resonance inhibition analysis of PpFucCS, IbFucCS, and IbSF against heparin binding to wildtype S-protein showed IC₅₀ values (in the nanomolar range) 6, 25, and 6 times more efficient than heparin, respectively. Data from computational simulations suggest an influence of the sulfation patterns of the Fuc units on hydrogen bonding with GlcA and that conformational change of some of the oligosaccharide structures occurs upon S-protein RBD binding. Compared with heparin, negligible anticoagulant action was observed for IbSF. Our results suggest that IbSF may represent a promising molecule for future investigations against SARS-CoV-2.