The management of a foodborne outbreak depends on the rapid and accurate identification of the responsible food source. Conventional methods based on isolation of the pathogen from the food matrix and target-specific real-time polymerase chain reactions (qPCRs) are used in routine. In recent years, the use of whole genome sequencing (WGS) of bacterial isolates has proven its value to collect relevant information for strain characterization as well as tracing the origin of the contamination by linking the food isolate with the patient’s isolate with high resolution. However, the isolation of a bacterial pathogen from food matrices is often time-consuming and not always successful. Therefore, we aimed to improve outbreak investigation by developing a method that can be implemented in reference laboratories to characterize the pathogen in the food vehicle without its prior isolation and link it back to human cases. We tested and validated a shotgun metagenomics approach by spiking food pathogens in specific food matrices using the Shiga toxin-producing (STEC) as a case study. Different DNA extraction kits and enrichment procedures were investigated to obtain the most practical workflow. We demonstrated the feasibility of shotgun metagenomics to obtain the same information as in ISO/TS 13136:2012 and WGS of the isolate in parallel by inferring the genome of the contaminant and characterizing it in a shorter timeframe. This was achieved in food samples containing different strains, including a combination of different STEC strains. For the first time, we also managed to link individual strains from a food product to isolates from human cases, demonstrating the power of shotgun metagenomics for rapid outbreak investigation and source tracking.