Hepatocellular carcinoma (HCC) is one of the leading causes of cancer-related deaths worldwide. Although sorafenib is a standard first-line molecule-targeted drug against advanced HCC, the drug resistance development and adverse side effects usually limit its efficacy. This study investigated the effect of fucoidan on the sorafenib sensitivity of sorafenib-resistant human HCC cell line HepG2-SR established by long-time exposure of HepG2 to sorafenib. We demonstrated fucoidan combined with sorafenib synergistically promoted apoptosis and cell cycle arrest whereas inhibited cell migration in HepG2-SR cells. This combination treatment effectively suppressed the cellular epithelial growth factor receptor (EGFR) nuclear distribution and downstream gene transcription. Interestingly, fucoidan bound the cell surface EGFR, dampening EGFR translocation to lipid raft and further nuclear distribution, restoring the sorafenib sensitivity in HepG2-SR cells. Blocking fucoidan-EGFR interaction using EGFR antibody restrained the enhanced anti-tumor effects upon the combined administration. Besides, EGFR knockdown abolished the combination treatment-improved anti-tumor efficacy. This combination also suppressed in vivo xenograft tumor growth in nude mice. Our present study uncovered that fucoidan overcame sorafenib resistance in HCC via its interaction with cell membrane EGFR and further suppression of EGFR redistribution and downstream signaling in sorafenib-resistant cells. Overall, current results suggest that simultaneous treatment of fucoidan and sorafenib might serve as a potential therapeutic strategy against sorafenib-resistant HCC.