Adequate calorie restriction (CR) as a healthy lifestyle is recommended not only for people with metabolic disorders but also for healthy adults. Previous studies have mainly focused on the beneficial metabolic effects of CR on obese subjects, while its effects on non-obese subjects are still scarce. Here, we conducted a three-week non-controlled CR intervention in 41 subjects, with approximately 40% fewer calories than the recommended daily energy intake. We measured BMI, and applied targeted metabolic profiling on fasting blood samples and shotgun metagenomic sequencing on fecal samples, before and after intervention. Subjects were stratified into two enterotypes according to their baseline microbial composition, including 28 enterotype Bacteroides (ETB) subjects and 13 enterotype Prevotella (ETP) subjects. CR decreased BMI in most subjects, and ETP subjects exhibited a significantly higher BMI loss ratio than the ETB subjects. Additionally, CR induced limited changes in gut microbial composition but substantial microbial-independent changes in blood AAs, including a significant increase in 3-methylhistidine, a biomarker of the skeletal muscle protein turnover. Finally, baseline abundances of seven microbial species, rather than baseline AA levels, could well predict CR-induced BMI loss. This non-controlled intervention study revealed associations between baseline gut microbiota and CR-induced BMI loss and provided evidence to accelerate the application of microbiome stratification in future personalized nutrition intervention.