Gene loss by deletion is a common evolutionary process in bacteria, as exemplified by bacteria with small genomes that have evolved from bacteria with larger genomes by reductive processes. The driving force(s) for genome reduction remains unclear, and here we examined the hypothesis that gene loss is selected because carriage of superfluous genes confers a fitness cost to the bacterium. In the bacterium Salmonella enterica, we measured deletion rates at 11 chromosomal positions and the fitness effects of several spontaneous deletions. Deletion rates varied over 200-fold between different regions with the replication terminus region showing the highest rates. Approximately 25% of the examined deletions caused an increase in fitness under one or several growth conditions, and after serial passage of wild-type bacteria in rich medium for 1,000 generations we observed fixation of deletions that substantially increased bacterial fitness when reconstructed in a non-evolved bacterium. These results suggest that selection could be a significant driver of gene loss and reductive genome evolution.