The genus Brevibacterium harbors many members important for cheese ripening. We performed real-time quantitative PCR (qPCR) to determine the abundance of Brevibacterium on rinds of Vorarlberger Bergkäse, an Austrian artisanal washed-rind hard cheese, over 160 days of ripening. Our results show that Brevibacterium are abundant on Vorarlberger Bergkäse rinds throughout the ripening time. To elucidate the impact of Brevibacterium on cheese production, we analysed the genomes of three cheese rind isolates, L261, S111, and S22. L261 belongs to Brevibacterium aurantiacum, whereas S111 and S22 represent novel species within the genus Brevibacterium based on 16S rRNA gene similarity and average nucleotide identity. Our comparative genomic analysis showed that important cheese ripening enzymes are conserved among the genus Brevibacterium. Strain S22 harbors a 22 kb circular plasmid which encodes putative iron and hydroxymethylpyrimidine/thiamine transporters. Histamine formation in fermented foods can cause histamine intoxication. We revealed the presence of a putative metabolic pathway for histamine degradation. Growth experiments showed that the three Brevibacterium strains can utilize histamine as the sole carbon source. The capability to utilize histamine, possibly encoded by the putative histamine degradation pathway, highlights the importance of Brevibacterium as key cheese ripening cultures beyond their contribution to cheese flavor production.