The survival, physiology and gene expression profile of the phenanthrene-degrading Sphingomonas sp. LH128 was examined after an extended period of complete nutrient starvation and compared with a non-starved population that had been harvested in exponential phase. After 6 months of starvation in an isotonic solution, only 5 % of the initial population formed culturable cells. Microscopic observation of GFP fluorescent cells, however, suggested that a larger fraction of cells (up to 80 %) were still alive and apparently had entered a viable but non-culturable (VBNC) state. The strain displayed several cellular and genetic adaptive strategies to survive long-term starvation. Flow cytometry, microscopic observation and fatty acid methyl ester (FAME) analysis showed a reduction in cell size, a change in cell shape and an increase in the degree of membrane fatty acid saturation. Transcriptome analysis showed decreased expression of genes involved in ribosomal protein biosynthesis, chromosomal replication, cell division and aromatic catabolism, increased expression of genes involved in regulation of gene expression and efflux systems, genetic translocations, and degradation of rRNA and fatty acids. Those phenotypic and transcriptomic changes were not observed after 4 h of starvation. Despite the starvation situation, the polycyclic aromatic hydrocarbon (PAH) catabolic activity was immediate upon exposure to phenanthrene. We conclude that a large fraction of cells maintain viability after an extended period of starvation apparently due to tuning the expression of a wide variety of cellular processes. Due to these survival attributes, bacteria of the genus Sphingomonas, like strain LH128, could be considered as suitable targets for use in remediation of nutrient-poor PAH-contaminated environments.