Mortality has a significant role in prokaryotic ecology and evolution, yet the impact of variations in extrinsic mortality on prokaryotic genome evolution has received little attention. We used both mathematical and agent-based models to reveal how variations in extrinsic mortality affect prokaryotic genome evolution. Our results suggest that the genome size of bacteria increases with increased mortality. A high extrinsic mortality increases the pool of free resources and shortens life expectancy, which selects for faster reproduction, a phenotype we called ‘scramblers’. This phenotype is realised by the expansion of gene families involved in nutrient acquisition and metabolism. In contrast, a low mortality rate increases an individual’s life expectancy, which results in natural selection favouring tolerance to starvation when conditions are unfavourable. This leads to the evolution of small, streamlined genomes (‘stayers’). Our models predict that large genomes, gene family expansion and horizontal gene transfer should be observed in prokaryotes occupying ecosystems exposed to high abiotic stress, as well as those under strong predator- and/or pathogen-mediated selection. A comparison of genome size of cyanobacteria in relatively stable marine versus more turbulent freshwater environments corroborates our predictions, although other factors between these environments could also be responsible.