Paenibacillus larvae is the causative agent of the fatal American foulbrood disease in honeybees (Apis mellifera). Strain identification is vital for preventing the spread of the disease. To date, the most accessible and robust scheme to identify strains is the multilocus sequence typing (MLST) method. However, this approach has limited resolution, especially for epidemiological studies. As the cost of whole-genome sequencing has decreased and as it becomes increasingly available to most laboratories, an extended MLST based on the core genome (cgMLST) presents a valuable tool for high-resolution investigations. In this study, we present a standardized, robust cgMLST scheme for P. larvae typing using whole-genome sequencing. A total of 333 genomes were used to identify, validate and evaluate 2419 core genes. The cgMLST allowed fine-scale differentiation between samples that had the same profile using traditional MLST and allowed for the characterization of strains impossible by MLST. The scheme was successfully used to trace a localized Swedish outbreak, where a cluster of 38 isolates was linked to a country-wide beekeeping operation. cgMLST greatly enhances the power of a traditional typing scheme, while preserving the same stability and standardization for sharing results and methods across different laboratories.