The human pathogen Listeria monocytogenes is a large concern in the food industry where its continuous detection in food products has caused a string of recalls in North America and Europe. Most recognized for its ability to grow in foods during refrigerated storage, L. monocytogenes can also tolerate several other food-related stresses with some strains possessing higher levels of tolerances than others. The objective of this study was to use a combination of phenotypic analyses and whole genome sequencing to elucidate potential relationships between L. monocytogenes genotypes and food-related stress tolerance phenotypes. To accomplish this, 166 L. monocytogenes isolates were sequenced and evaluated for their ability to grow in cold (4°C), salt (6% NaCl, 25°C), and acid (pH 5, 25°C) stress conditions as well as survive desiccation (33% RH, 20°C). The results revealed that the stress tolerance of L. monocytogenes is associated with serotype, clonal complex (CC), full length inlA profiles, and the presence of a plasmid which was identified in 55% of isolates. Isolates with full length inlA exhibited significantly (p < 0.001) enhanced cold tolerance relative to those harboring a premature stop codon (PMSC) in this gene. Similarly, isolates possessing a plasmid demonstrated significantly (p = 0.013) enhanced acid tolerance. We also identified nine new L. monocytogenes sequence types, a new inlA PMSC, and several connections between CCs and the presence/absence or variations of specific genetic elements. A whole genome single-nucleotide-variants phylogeny revealed sporadic distribution of tolerant isolates and closely related sensitive and tolerant isolates, highlighting that minor genetic differences can influence the stress tolerance of L. monocytogenes. Specifically, a number of cold and desiccation sensitive isolates contained PMSCs in σB regulator genes (rsbS, rsbU, rsbV). Collectively, the results suggest that knowing the sequence type of an isolate in addition to screening for the presence of full-length inlA and a plasmid, could help food processors and food agency investigators determine why certain isolates might be persisting in a food processing environment. Additionally, increased sequencing of L. monocytogenes isolates in combination with stress tolerance profiling, will enhance the ability to identify genetic elements associated with higher risk strains.