The lactic acid bacterium Leuconostoc pseudomesenteroides can be found in mesophilic cheese starters, where it produces aromatic compounds from, e.g., citrate. Here, we present the draft genome sequences of two L. pseudomesenteroides strains isolated from traditional Danish cheese starters.