ABSTRACT Deep sequencing has revolutionized our understanding of the bacterial RNA world and has facilitated the identification of 280 small RNAs (sRNAs) in Salmonella . Despite the suspicions that sRNAs may play important roles in Salmonella pathogenesis, the functions of most sRNAs remain unknown. To advance our understanding of RNA biology in Salmonella virulence, we searched for sRNAs required for bacterial invasion into nonphagocytic cells. After screening 75 sRNAs, we discovered that the ablation of InvS caused a significant decrease of Salmonella invasion into epithelial cells. A proteomic analysis showed that InvS modulated the levels of several type III secreted Salmonella proteins. The level of PrgH, a type III secretion apparatus protein, was significantly lower in the absence of InvS, consistent with the known roles of PrgH in effector secretion and bacterial invasion. We discovered that InvS modulates fimZ expression and hence flagellar gene expression and motility. We propose that InvS coordinates the increase of PrgH and decrease in FimZ that promote efficient Salmonella invasion into nonphagocytic cells. IMPORTANCE Salmonellosis continues to be the most common foodborne infection reported by the CDC in the United States. Central to Salmonella pathogenesis is the ability to invade nonphagocytic cells and to replicate inside host cells. Invasion genes are known to be regulated by protein transcriptional networks, but little is known about the role played by small RNAs (sRNAs) in this process. We have identified a novel sRNA, InvS, that is involved in Salmonella invasion. Our result will likely provide an opportunity to better understand the fundamental question of how Salmonella regulates invasion gene expression and may inform strategies for therapeutic intervention.