There is a lack of direct evidence regarding gut microbiota dysbiosis and changes in short-chain fatty acids (SCFAs) in heart failure (HF) patients. We sought to assess any association between gut microbiota composition, SCFA production, clinical parameters, and the inflammatory profile in a cohort of newly diagnosed HF patients. In this longitudinal prospective study, we enrolled eighteen newly diagnosed HF patients. At admission and after 12 months, blood samples were collected for the assessment of proinflammatory cytokines, monocyte populations, and endothelial dysfunction, and stool samples were collected for analysis of gut microbiota composition and quantification of SCFAs. Twelve months after the initial HF episode, patients demonstrated improved clinical parameters and reduced inflammatory state and endothelial dysfunction. This favorable evolution was associated with a reversal of microbiota dysbiosis, consisting of the increment of health-related bacteria, such as genus Bifidobacterium, and levels of SCFAs, mainly butyrate. Furthermore, there was a decrease in the abundance of pathogenic bacteria. In vitro, fecal samples collected after 12 months of follow-up exhibited lower inflammation than samples collected at admission. In conclusion, the favorable progression of HF patients after the initial episode was linked to the reversal of gut microbiota dysbiosis and increased SCFA production, particularly butyrate. Whether restoring butyrate levels or promoting the growth of butyrate-producing bacteria could serve as a complementary treatment for these patients deserves further studies.