Flavor perception is a key factor in the acceptance or rejection of food. Aroma precursors such as cysteine conjugates are present in various plant-based foods and are metabolized into odorant thiols in the oral cavity. To date, the involved enzymes are unknown, despite previous studies pointing out the likely involvement of carbon–sulfur lyases (C–S lyases) from the oral microbiota. In this study, we show that saliva metabolizes allyl-cysteine into odorant thiol metabolites, with evidence suggesting that microbial pyridoxal phosphate-dependent C–S lyases are involved in the enzymatic process. A phylogenetic analysis of PatB C–S lyase sequences in four oral subspecies of Fusobacterium nucleatum was carried out and led to the identification of several putative targets. FnaPatB1 from F. nucleatum subspecies animalis, a putative C–S lyase, was characterized and showed high activity with a range of cysteine conjugates. Enzymatic and X-ray crystallographic data showed that FnaPatB1 metabolizes cysteine derivatives within a unique active site environment that enables the formation of flavor sulfur compounds. Using an enzymatic screen with a library of pure compounds, we identified several inhibitors able to reduce the C–S lyase activity of FnaPatB1 in vitro, which paves the way for controlling the release of odorant sulfur compounds from their cysteine precursors in the oral cavity.