Intestinal microbiota changes are associated with the development of obesity. However, studies in humans have generated conflicting results due to high inter-individual heterogeneity in terms of diet, age, and hormonal factors, and the largely unexplored influence of gender. In this work, we aimed to identify differential gut microbiota signatures associated with obesity, as a function of gender and changes in body mass index (BMI). Differences in the bacterial community structure were analyzed by 16S sequencing in 39 men and 36 post-menopausal women, who had similar dietary background, matched by age and stratified according to the BMI. We observed that the abundance of the Bacteroides genus was lower in men than in women (P<0.001, Q = 0.002) when BMI was > 33. In fact, the abundance of this genus decreased in men with an increase in BMI (P<0.001, Q<0.001). However, in women, it remained unchanged within the different ranges of BMI. We observed a higher presence of Veillonella (84.6% vs. 47.2%; X2 test P = 0.001, Q = 0.019) and Methanobrevibacter genera (84.6% vs. 47.2%; X2 test P = 0.002, Q = 0.026) in fecal samples in men compared to women. We also observed that the abundance of Bilophila was lower in men compared to women regardless of BMI (P = 0.002, Q = 0.041). Additionally, after correcting for age and sex, 66 bacterial taxa at the genus level were found to be associated with BMI and plasma lipids. Microbiota explained at P = 0.001, 31.17% variation in BMI, 29.04% in triglycerides, 33.70% in high-density lipoproteins, 46.86% in low-density lipoproteins, and 28.55% in total cholesterol. Our results suggest that gut microbiota may differ between men and women, and that these differences may be influenced by the grade of obesity. The divergence in gut microbiota observed between men and women might have a dominant role in the definition of gender differences in the prevalence of metabolic and intestinal inflammatory diseases.