The genera Leuconostoc, Oenococcus, and Weissella (family “Leuconostocaceae”) constitute a group of lactic acid bacteria of great interest in food microbiology. From the taxonomic point of view, they are considered phylogenetically coherent according to their 16S rRNA gene sequences and other macromolecules. These three genera were the focus of the present study; specifically, the resolution and discriminatory power of recN (encoding a DNA repair and genetic recombination protein) as a molecular marker at the species level were investigated. For this purpose, partial sequences (about 1200 nt) were obtained from 23 type strains and from several additional strains following direct amplification of recN and subsequent sequencing. Phylogeny was evaluated according to different treeing methods (neighbor joining, maximum likelihood, and maximum parsimony) and the inclusion of variability filters. The results showed that recN, used either alone or in combination with 16S rRNA data, can serve as a phylogenetic marker as well as a tool for species identification.