Modelling the emergence of foodborne pathogens is a crucial step in the prediction and prevention of disease outbreaks. Unfortunately, the mechanisms that drive the evolution of such continuously adapting pathogens remain poorly understood. Here, we combine molecular genotyping with network science and Bayesian inference to infer directed genotype networks-and trace the emergence and evolutionary paths-of Salmonella Typhimurium (STM) from nine years of Australian disease surveillance data. We construct networks where nodes represent STM strains and directed edges represent evolutionary steps, presenting evidence that the structural (i.e., network-based) features are relevant to understanding the functional (i.e., fitness-based) progression of co-evolving STM strains. This is argued by showing that outbreak severity, i.e., prevalence, correlates to: (i) the network path length to the most prevalent node (r = -0.613, N = 690); and (ii) the network connected-component size (r = 0.739). Moreover, we uncover distinct exploration-exploitation pathways in the genetic space of STM, including a strong evolutionary drive through a transition region. This is examined via the 6,897 distinct evolutionary paths in the directed network, where we observe a dominant 66% of these paths decrease in network centrality, whilst increasing in prevalence. Furthermore, 72.4% of all paths originate in the transition region, with 64% of those following the dominant direction. Further, we find that the length of an evolutionary path strongly correlates to its increase in prevalence (r = 0.497). Combined, these findings indicate that longer evolutionary paths result in genetically rare and virulent strains, which mostly evolve from a single transition point. Our results not only validate our widely-applicable approach for inferring directed genotype networks from data, but also provide a unique insight into the elusive functional and structural drivers of STM bacteria.