Denitrifying bioelectrochemical systems (d-BES) are a promising technology for nitrate removal from wastewaters. Microbial community monitoring is required to pave the way to application. In this study, for the first time flow cytometry combined with molecular biology techniques is exploited to monitor and determine the structure–function relationship of the microbiome of a denitrifying biocathode. Stable cathode performance at poised potential (−0.32 V vs. Ag/AgCl) was monitored, and different stress-tests were applied (reactor leakage, nitrate concentration, buffer capacity). Stress-tests shifted the reactor microbiome and performance. The monitoring campaign covered a wide range of nitrate consumption rates (from 15 to 157 mg N LNCC−1 d−1), current densities (from 0 to 25 mA LNCC−1) and denitrification intermediates (nitrite and nitrous oxide consumption rates varied from 0 to 56 mg N LNCC−1 d−1). The reactor microbiome (composed of 21 subcommunities) was characterized and its structure–function relationship was revealed. A key role for Thiobacillus sp. in the bioelectrochemical reduction of nitrate was suggested, while a wider number of subcommunities were involved in NO2− and N2O reduction. It was demonstrated that different bacteria catalyze each denitrification step in a biocathode. This study contributed significantly to understanding denitrifying biocathodes, paving the way for their knowledge-driven engineering.