Background: In nature, microorganisms have to adapt to long-term stressful conditions often with growth limitations. However, little is known about the evolution of the adaptability of new bacteria to such environments. Pseudomonas aeruginosa, an opportunistic pathogen, after natural evaporation of seawater, was shown to be trapped in laboratory-grown halite crystals and to remain viable after entrapment for years. However, how this bacterium persists and survives in such hypersaline conditions is not understood. Results: In this study, we aimed to understand the basis of survival, and to characterise the physiological changes required to develop salt tolerance using P. aeruginosa as a model. Several clones of P. aeruginosa were rescued after 14 years in naturally evaporated marine salt crystals. Incubation of samples in nutrient-rich broth allowed re-growth and subsequent plating yielded observable colonies. Whole genome sequencing of the P. aeruginosa isolates confirmed the recovery of the original strain. The re-grown strains, however, showed a new phenotype consisting of an enhanced growth in growing salt concentration compared to the ancestor strain. The intracellular accumulation of K⁺ was elicited by high concentration of Na⁺ in the external medium to maintain the homeostasis. Whole transcriptomic analysis by microarray indicated that 78 genes had differential expression between the parental strain and its derivative clones. Sixty-one transcripts were up-regulated, while 17 were down-regulated. Based on a collection of single-gene knockout mutants and gene ontology analysis, we suggest that the adaptive response in P. aeruginosa to hyper-salinity relies on multiple gene product interactions. Conclusions: The individual gene contributions build up the observed phenotype, but do not ease the identification of salinity-related metabolic pathways. The long-term inclusion of P. aeruginosa in salt crystals primes the bacteria, mediating a readjustment of the bacterial physiology to growth in higher salt concentrations. Our findings provide a starting point to understand how P. aeruginosa, a relevant environmental and pathogenic bacterium, survives to long-term salt stress.