Gut microbiota (GM) is considered to play an important role in obesity. Additionally, the impact of dietary fiber (DF) consumption on GM has been well established. Brown seaweeds are known to be a rich source of DF. However, the effect of insoluble DFs (IDFs) alone from brown seaweed on obesity and GM remains to be determined. This study investigated the effect of IDFs prepared from Laminaria japonica Aresch on high-fat diet (HFD)-induced obesity and GM dysbiosis in mice. Although HFD-induced body weight gain was not significantly attenuated by the IDF treatment, HFD-induced liver injury was ameliorated, and the HFD-elevated serum cholesterol concentration and glucose level of obese mice were significantly lowered. IDF treatment significantly modulated the GM composition disturbed by the HFD. It was found that 5% IDFs restored the GM to a very similar composition to that in the normal mice. The relative abundance of Akkermansia genus was decreased by >300-fold in HFD-fed mice, and it was fully restored by 5% IDF administration. Akkermansia muciniphila, a short-chain fatty acid producer, was identified as a marker species in both control and high-dose IDF groups. Furthermore, IDFs significantly restored the HFD-reduced acetate and propionate levels in the cecal content. In conclusion, the beneficial effect of IDFs derived from L. japonica on obesity was confirmed in mice, and the underlying mechanism may be associated with the modulation of GM composition, possibly through the enrichment of Akkermansia.