Purpose Obesity has been related to intestinal dysbiosis and the modification of gut microbiota composition by dietary strategies becomes a promising strategy to help manage obesity. The aim of the current study was to evaluate the effect of two weight-loss diets on the composition and functional profile of gut microbiota. Methods 55 men and 124 women with BMI > 25 kg/m(2) were randomly assigned to moderately high-protein (MHP) or low-fat (LF) diet. Differences in fecal bacteria abundance (based on 16 s rRNA sequencing) between before and after 4 months of calorie restriction was analyzed using EdgeR tool in MicrobiomeAnalyst platform. Bacterial functional profile was predicted using Tax4Fun and metagenomeSeq analysis. Significant KEGG Orthology (KO) terms were selected for the metabolomic study using chromatography. Results After the intervention, MHP-men showed a significant decrease in Negativicutes, Selenomonadales, Dielma and Dielma fastidiosa. LF-men showed a significant increase in Bacilli, Lactobacillales, Christensenellaceae, Peptococcaceae, and Streptococcaceae, Peptococcus, Streptococcus and Christensenella, Duncaniella dubosii_CP039396_93.49%, Roseburia sp_AB744234_98.96% and Alistipes inops_KJ572413_99.57%. MHP-women increased Pasteurellales, Phascolarctobacterium succinatutens, Ruthenibacterium lactatiformans_LR215981_99.55% and decreased in Phascolarctobacterium succinatutens_NR112902_99.56%. Finally, LF-women presented a significant decrease in Bacteroides clarus and Erysipelothrix inopinata_CP060715_84.4%. Surprisingly, no matching bacterial changes were found between these four groups. A total of 42 KO, 10 metabolic pathways and 107 related metabolites related were found implicated in these bacterial changes. Seven metabolites were confirmed in plasma. Conclusion Weight-loss-related-changes in gut microbiome composition and the functional profile occur in a sex- and diet-related manner, showing that women and men could differentially benefit from the consumption of MHP and LF diets.