Bariatric surgery is currently the most effective procedure for the treatment of obesity. Given the role of the gut microbiota in regulating host metabolism and adiposity, we investigated the long-term effects of bariatric surgery on the microbiome of patients randomized to Roux-en-Y gastric bypass or vertical banded gastroplasty and matched for weight and fat mass loss. The two surgical procedures induced similar and durable changes on the gut microbiome that were not dependent on body mass index and resulted in altered levels of fecal and circulating metabolites compared with obese controls. By colonizing germ-free mice with stools from the patients, we demonstrated that the surgically altered microbiota promoted reduced fat deposition in recipient mice. These mice also had a lower respiratory quotient, indicating decreased utilization of carbohydrates as fuel. Our results suggest that the gut microbiota may play a direct role in the reduction of adiposity observed after bariatric surgery.