The conversion of methionine to volatile sulfur compounds (VSCs) is of great importance in flavor formation during cheese ripening and is the focus of biotechnological approaches toward flavor improvement. A synthetic mgl gene encoding methionine-gamma-lyase (MGL) from Brevibacterium linens BL2 was cloned into a Lactococcus lactis expression plasmid under the control of the nisin-inducible promoter PnisA. When expressed in L. lactis and purified as a recombinant protein, MGL was shown to degrade L-methionine as well as other sulfur-containing compounds such as L-cysteine, L-cystathionine, and L-cystine. Overproduction of MGL in recombinant L. lactis also resulted in an increase in the degradation of these compounds compared to the wild-type strain. Importantly, gas chromatography-mass spectrometry analysis identified considerably higher formation of methanethiol (and its oxidized derivatives dimethyl disulfide and dimethyl trisulfide) in reactions containing either purified protein, whole cells, or cell extracts from the heterologous L. lactis strain. This is the first report of production of MGL from B. linens in L. lactis. Given their significance in cheese flavor development, the use of lactic acid bacteria with enhanced VSC-producing abilities could be an efficient way to enhance cheese flavor development.