The emergence of pathogenic strains of enteric bacteria and their adaptation to unique niches are associated with the acquisition of foreign DNA segments termed ‘genetic islands’. We explored these islands for the occurrence of small RNA (sRNA) encoding genes. Previous systematic screens for enteric bacteria sRNAs were mainly carried out using the laboratory strain Escherichia coli K12, leading to the discovery of ∼80 new sRNA genes. These searches were based on conservation within closely related members of enteric bacteria and thus, sRNAs, unique to pathogenic strains were excluded. Here we describe the identification and characterization of 19 novel unique sRNA genes encoded within the ‘genetic islands’ of the virulent strain Salmonella typhimurium. We show that the expression of many of the island-encoded genes is associated with stress conditions and stationary phase. Several of these sRNA genes are induced when Salmonella resides within macrophages. One sRNA, IsrJ, was further examined and found to affect the translocation efficiency of virulence-associated effector proteins into nonphagocytic cells. In addition, we report that unlike the majority of the E. coli sRNAs that are trans regulators, many of the island-encoded sRNAs affect the expression of cis-encoded genes. Our study suggests that the island encoded sRNA genes play an important role within the network that regulates bacterial adaptation to environmental changes and stress conditions and thus controls virulence.