We studied the structure of fucoidans extracted from two brown seaweed species, Sargassum crassifolium and Padina australis, and their intestinal immunomodulating activity via Peyer’s patch cells of C3H/HeJ mice. ESI–MS analysis indicated that the dominant structure of both fucoidans has a backbone of α-(1→4)-linked and α-(1→3)-linked l-fucose residues and sulfate groups are attached at the C-2 and C-4 positions; branches of fucoidan from S. crassifolium are galactose residues with (1→4)- linkage and branching points are at C-4 of fucose, while fucoidan from P. australis, branches are sulfated galactose-fucose disaccharides and sulfated galactose monosaccharides attached to the main chain through (1→3)- or (1→4)- linkages. According to small angle X-ray scattering (SAXS) measurements, the two fucoidans have a branched structure. We simulated them with molecular models based on our proposed primary structure. These fucoidan samples have the ability to stimulate intestinal immunological activity via Peyer’s patch cells.