The Ralstonia solanacearum species complex (RSSC) is a highly diverse cluster of bacterial strains found worldwide, many of which are destructive and cause bacterial wilt (BW) in a wide range of host plants. In 2009, potato production in Madagascar was dramatically affected by several BW epidemics. Controlling this disease is critical for Malagasy potato producers. The first important step toward control is the characterization of strains and their putative origins. The genetic diversity and population structure of the RSSC were investigated in the major potato production areas of the Highlands. A large collection of strains (n = 1224) was assigned to RSSC phylotypes based on multiplex polymerase chain reaction (PCR). Phylotypes I and III have been present in Madagascar for a long time but rarely associated with major potato BW outbreaks. The marked increase of BW prevalence was found associated with phylotype IIB sequevar 1 (IIB-1) strains (n = 879). This is the first report of phylotype IIB-1 strains in Madagascar. In addition to reference strains, epidemic IIB-1 strains (n = 255) were genotyped using the existing MultiLocus Variable-Number Tandem Repeat Analysis (MLVA) scheme RS2-MLVA9, producing 31 haplotypes separated into two related clonal complexes (CCs). One major CC included most of the worldwide haplotypes distributed across wide areas. A regional-scale investigation suggested that phylotype IIB-1 strains were introduced and massively spread via latently infected potato seed tubers. Additionally, the genetic structure of phylotype IIB-1 likely resulted from a bottleneck/founder effect. The population structure of phylotype III, described here for the first time in Madagascar, exhibited a different pattern. Phylotype III strains (n = 217) were genotyped using the highly discriminatory MLVA scheme RS3-MLVA16. High genetic diversity was uncovered, with 117 haplotypes grouped into 11 CCs. Malagasy phylotype III strains were highly differentiated from continental African strains, suggesting no recent migration from the continent. Overall, population structure of phylotype III involves individual small CCs that correlate to restricted geographic areas in Madagascar. The evidence suggests, if at all, that African phylotype III strains are not efficiently transmitted through latently infected potato seed tubers.