Sensing and responding to environmental cues is a fundamental characteristic of bacterial physiology and virulence. Here we identify polyamines as novel environmental signals essential for virulence of Salmonella enterica serovar Typhimurium, a major food borne intracellular pathogen and a model organism for studying typhoid fever. Central to its virulence are two major virulence loci Salmonella Pathogenicity Island 1 and 2 (SPI1 and SPI2). SPI1 promotes invasion of epithelial cells, whereas SPI2 enables S. Typhimurium to survive and proliferate within specialized compartments inside host cells. In this study, we show that an S. Typhimurium polyamine mutant is defective for invasion, intracellular survival, killing of the nematode Caenorhabditis elegans and systemic infection of the mouse model of typhoid fever. Virulence of the mutant could be restored by genetic complementation, and invasion and intracellular survival could, as well, be complemented by the addition of exogenous polyamines to the bacterial cultures prior to infection. Experiments addressed at elucidating the roles of polyamines in infection revealed that expression of genes from both of the major virulence loci SPI1 and SPI2 responded to exogenous polyamines and was reduced in the polyamine mutant. Further molecular characterization of polyamine dependent expression of virulence revealed complex cross-talk between known regulators of virulence expression and polyamines. Together our data demonstrate that polyamines play a critical role in controlling virulence in S. Typhimurium most likely through stimulation of expression of essential virulence loci. Moreover, our data implicate polyamines as key signals in S. Typhimurium virulence.