Genotyping of Klebsiella pneumoniae is indispensable for management of nosocomial infections, monitoring of emerging strains -including extended-spectrum beta-lactamase (ESBL) producers-, and general epidemiology. Such objectives require a high-resolution genotyping method with a fixed scheme that allows (1) long-term retrospective and prospective assessment, (2) objective result readout and (3) library storage for database development and exchangeable results. We have developed a multiple-locus variable number tandem repeat analysis (MLVA) using a single-tube fluorescently primed multiplex PCR for 8 Variable Number Tandem Repeats (VNTRs) and automated fragment size analysis. The type allocation scheme was optimized using 224 K. pneumoniae clinical isolates, which yielded 101 MLVA types. The method was compared to the gold standard multilocus sequence typing (MLST) using a subset of these clinical isolates (n = 95) and found to be highly concordant, with at least as high a resolution but with considerably less hands-on time. Our results position this MLVA scheme as an appropriate, high-throughput and relatively low-cost tool for K. pneumoniae epidemiology.