Salmonella spp. possess a conserved type III secretion system encoded within the pathogenicity island 1 (SPI1; centisome 63), which mediates translocation of effector proteins into the host cell cytosol to trigger responses such as bacterial internalization. Several translocated effector proteins are encoded in other regions of the Salmonella chromosome. It remains unclear how this complex chromosomal arrangement of genes for the type III apparatus and the effector proteins emerged and how the different effector proteins cooperate to mediate virulence. By Southern blotting, PCR, and phylogenetic analyses of highly diverse Salmonella spp., we show here that effector protein genes located in the core of SPI1 are present in all Salmonella lineages. Surprisingly, the same holds true for several effector protein genes located in distant regions of the Salmonella chromosome, namely, sopB (SPI5, centisome 20), sopD (centisome 64), and sopE2 (centisomes 40 to 42). Our data demonstrate that sopB, sopD, and sopE2, along with SPI1, were already present in the last common ancestor of all contemporary Salmonella spp. Analysis of Salmonella mutants revealed that host cell invasion is mediated by SopB, SopE2, and, in the case of Salmonella enterica serovar Typhimurium SL1344, by SopE: a sopB sopE sopE2-deficient triple mutant was incapable of inducing membrane ruffling and was >100-fold attenuated in host cell invasion. We conclude that host cell invasion emerged early during evolution by acquisition of a mosaic of genetic elements (SPI1 itself, SPI5 [sopB], and sopE2) and that the last common ancestor of all contemporary Salmonella spp. was probably already invasive.