Multi-locus sequence typing (MLST) based on eight genes has become the method of choice for Borrelia typing and is extensively used for population studies. Whole-genome sequencing enables studies to scale up to genomic levels but necessitates extended schemes. We have developed a 639-loci core genome MLST (cgMLST) scheme for Borrelia burgdorferi sensu lato (s.l.) that enables unambiguous genotyping and improves the robustness of phylogenies and lineage resolution within species. Notably, all inner nodes of the cgMLST phylogenies had consistently high statistical support. Analyses of the genetically homogeneous European B. bavariensis population support the notion that cgMLST provides high discriminatory power even for closely related isolates. While isolates differed maximally in one MLST locus, there were up to 179 cgMLST loci differences. Thus, the developed cgMLST scheme for B. burgdorferi s.l. resolves lineages at a finer resolution than MLST and improves insights into the evolutionary history of the species complex.