Fucoidan represents fucose-rich sulfated polysaccharides derived from brown seaweeds, which exerts various biological activities applicable for functional foods and therapeutic agents. The objective of the present study was to investigate in vivo effects of fucoidan extracted from Okinawa mozuku (Cladosiphon okamuranus), common edible seaweed in Japan, on immune responses and microbiota composition in zebrafish. We treated larvae and adult zebrafish with Okinawa mozuku (OM) fucoidan by immersion (100 and 500 μg/mL, 3 days) and by feeding (3 weeks), respectively. The effect of OM fucoidan on immune responses in zebrafish larvae was evaluated by live imaging of neutrophils and macrophages as well as quantitative polymerase chain reaction of pro- and anti-inflammatory cytokine genes. Whole microbiota of zebrafish larvae and intestinal microbiota of adult zebrafish treated with OM fucoidan were analyzed by Illumina MiSeq pair-end sequencing of the V3-V4 region of 16S rRNA genes. Fucoidan treatment only slightly affected the composition of the larvae microbiota and the number of neutrophils and macrophages, while pro- and anti-inflammatory cytokine gene expression levels were upregulated in the larvae treated with 500 μg/mL OM fucoidan. In contrast, feeding of OM fucoidan clearly altered the intestinal microbiota composition of adult zebrafish, which was characterized by the emergence and predominance of multiple bacterial operational taxonomic units (OTUs) affiliated with Rhizobiaceae and Comamonadaceae at the expense of E. coli-related Enterobacteriaceae, the dominant OTUs throughout the studied samples. These changes were accompanied by decreased expression levels of pro-inflammatory cytokine il1b in the intestines of the adult zebrafish. Our current study provides the first insights into in vivo modulatory effects of fucoidan on microbiota and immune responses of unchallenged zebrafish, which underscores the potential of fucoidan to play a modulatory role in the diet-microbiota-host interplay.