Enteroinvasive Escherichia coli (EIEC) and Shigella are closely related agents of bacillary dysentery. It is widely viewed that EIEC and Shigella species evolved from E. coli via independent acquisitions of a large virulence plasmid (pINV) encoding a type 3 secretion system (T3SS). Sequence Type (ST)99 O96:H19 E. coli is a novel clone of EIEC responsible for recent outbreaks in Europe and South America. Here, we use 92 whole genome sequences to reconstruct a dated phylogeny of ST99 E. coli, revealing distinct phylogenomic clusters of pINV-positive and -negative isolates. To study the impact of pINV acquisition on the virulence of this clone, we developed an EIEC-zebrafish infection model showing that virulence of ST99 EIEC is thermoregulated. Strikingly, zebrafish infection using a T3SS-deficient ST99 EIEC strain and the oldest available pINV-negative isolate reveals a separate, temperature-independent mechanism of virulence, indicating that ST99 non-EIEC strains were virulent before pINV acquisition. Taken together, these results suggest that an already pathogenic E. coli acquired pINV and that virulence of ST99 isolates became thermoregulated once pINV was acquired. IMPORTANCE Enteroinvasive Escherichia coli (EIEC) and Shigella are etiological agents of bacillary dysentery. Sequence Type (ST)99 is a clone of EIEC hypothesized to cause human disease by the recent acquisition of pINV, a large plasmid encoding a type 3 secretion system (T3SS) that confers the ability to invade human cells. Using Bayesian analysis and zebrafish larvae infection, we show that the virulence of ST99 EIEC isolates is highly dependent on temperature, while T3SS-deficient isolates encode a separate temperature-independent mechanism of virulence. These results indicate that ST99 non-EIEC isolates may have been virulent before pINV acquisition and highlight an important role of pINV acquisition in the dispersal of ST99 EIEC in humans, allowing wider dissemination across Europe and South America.