On the basis of the abundance of specific bacterial genera, the human gut microbiota can be divided into two relatively stable groups that might have a role in personalized nutrition. We studied these simplified enterotypes as prognostic markers for successful body fat loss on two different diets. A total of 62 participants with increased waist circumference were randomly assigned to receive an ad libitum New Nordic Diet (NND) high in fiber/whole grain or an Average Danish Diet for 26 weeks. Participants were grouped into two discrete enterotypes by their relative abundance of Prevotella spp. divided by Bacteroides spp. (P/B ratio) obtained by quantitative PCR analysis. Modifications of dietary effects of pre-treatment P/B group were examined by linear mixed models. Among individuals with high P/B the NND resulted in a 3.15 kg (95% confidence interval (CI): 1.55; 4.76, P < 0.001) larger body fat loss compared with ADD, whereas no differences was observed among individuals with low P/B (0.88 kg (95% CI: -0.61; 2.37, P = 0.25)). Consequently, a 2.27 kg (95% CI: 0.09; 4.45, P = 0.041) difference in responsiveness to the diets were found between the two groups. In summary, subjects with high P/B ratio appeared more susceptible to lose body fat on diets high in fiber and whole grain than subjects with a low P/B ratio.