The intestinal pathogen Salmonella enterica rapidly enters the bloodstream after the invasion of intestinal epithelial cells, but how Salmonella breaks through the gut-vascular barrier is largely unknown. Here, we report that Salmonella enters the bloodstream through intestinal CX3CR1 macrophages during early infection. Mechanistically, Salmonella induces the migration/invasion properties of macrophages in a manner dependent on host cell actin and on the pathogen effector SteC. SteC recruits host myosin light chain protein Myl12a and phosphorylates its Ser19 and Thr20 residues. Myl12a phosphorylation results in actin rearrangement, and enhanced migration and invasion of macrophages. SteC is able to utilize a wide range of NTPs other than ATP to phosphorylate Myl12a. We further solved the crystal structure of SteC, which suggests an atypical dimerization-mediated catalytic mechanism. Finally, in vivo data show that SteC-mediated cytoskeleton manipulation is crucial for Salmonella breaching the gut vascular barrier and spreading to target organs.