Histamine production from histidine in fermented food products by lactic acid bacteria results in food spoilage and is harmful to consumers. We have isolated a histamine-producing lactic acid bacterium, Lactobacillus hilgardii strain IOEB 0006, which could retain or lose the ability to produce histamine depending on culture conditions. The hdcA gene, coding for the histidine decarboxylase of L. hilgardii IOEB 0006, was located on an 80-kb plasmid that proved to be unstable. Sequencing of the hdcA locus disclosed a four-gene cluster encoding the histidine decarboxylase, a protein of unknown function, a histidyl-tRNA synthetase, and a protein, which we named HdcP, showing similarities to integral membrane transporters driving substrate/product exchange. The gene coding for HdcP was cloned downstream of a sequence specifying a histidine tag and expressed in Lactococcus lactis. The recombinant HdcP could drive the uptake of histidine into the cell and the exchange of histidine and histamine. The combination of HdcP and the histidine decarboxylase forms a typical bacterial decarboxylation pathway that may generate metabolic energy or be involved in the acid stress response. Analyses of sequences present in databases suggest that the other two proteins have dispensable functions. These results describe for the first time the genes encoding a histamine-producing pathway and provide clues to the parsimonious distribution and the instability of histamine-producing lactic acid bacteria.