Major depressive disorder (MDD) is among the most prevalent mental disorders worldwide. Factors causing the pathogenesis of MDD include gut microbiota (GM), which interacts with the host through the gut–brain axis. In previous studies of GM in MDD patients, 16S rRNA sequencing was used, which provided information about composition but not about function. In our study, we analyzed whole metagenome sequencing data to assess changes in both the composition and functional profile of GM. We looked at the GM of 36 MDD patients, compared with that of 38 healthy volunteers. Comparative taxonomic analysis showed decreased abundances of Faecalibacterium prausnitzii, Roseburia hominis, and Roseburia intestinalis, and elevated abundances of Escherichia coli and Ruthenibacterium lactatiformans in the GM of MDD patients. We observed decreased levels of bacterial genes encoding key enzymes involved in the production of arginine, asparagine, glutamate, glutamine, melatonin, acetic, butyric and conjugated linoleic acids, and spermidine in MDD patients. These genes produced signature pairs with Faecalibacterium prausntizii and correlated with decreased levels of this species in the GM of MDD patients. These results show the potential impact of the identified biomarker bacteria and their metabolites on the pathogenesis of MDD, and should be confirmed in future metabolomic studies.