The intestinal microbiome is essential for human health. Significant differences in microbiota compositions have been found between individuals, but the impact that sex has on the gut microbiota alterations during obesity alleviation via fish oil and krill oil treatments is unknown. In this study, male and female high-fat-diet induced obese ICR mice received 600 μg g d fish oil, krill oil, or a mixture of both (1:1, 600 μg g d) continuously for 12 weeks. Our results indicated that the oil treatment had a greater efficacy in alleviating obesity in male mice compared with female mice, and the overall structures of the gut microbiota were notably different. Three operational taxonomic units (OTUs) were identified that were highly associated with the obesity phenotype in male mice, while 14 such OTUs were identified in female mice. These findings demonstrated that the alteration of the gut microbiota after fish and krill oil supplementation in mice is sex-associated.