The gut microbiome is emerging as a key regulator of several metabolic, immune and neuroendocrine pathways1,2. Gut microbiome deregulation has been implicated in major conditions such as obesity, type 2 diabetes, cardiovascular disease, non-alcoholic fatty acid liver disease and cancer3-6, but its precise role in aging remains to be elucidated. Here, we find that two different mouse models of progeria are characterized by intestinal dysbiosis with alterations that include an increase in the abundance of Proteobacteria and Cyanobacteria, and a decrease in the abundance of Verrucomicrobia. Consistent with these findings, we found that human progeria patients also display intestinal dysbiosis and that long-lived humans (that is, centenarians) exhibit a substantial increase in Verrucomicrobia and a reduction in Proteobacteria. Fecal microbiota transplantation from wild-type mice enhanced healthspan and lifespan in both progeroid mouse models, and transplantation with the verrucomicrobia Akkermansia muciniphila was sufficient to exert beneficial effects. Moreover, metabolomic analysis of ileal content points to the restoration of secondary bile acids as a possible mechanism for the beneficial effects of reestablishing a healthy microbiome. Our results demonstrate that correction of the accelerated aging-associated intestinal dysbiosis is beneficial, suggesting the existence of a link between aging and the gut microbiota that provides a rationale for microbiome-based interventions against age-related diseases.