Sphingomonas sp. strain RB2256 is representative of the ultramicrobacteria that proliferate in oligotrophic marine waters. While this class of bacteria is well adapted for growth with low concentrations of nutrients, their ability to respond to complete nutrient deprivation has not previously been investigated. In this study, we examined two-dimensional protein profiles for logarithmic and stationary-phase cells and found that protein spot intensity was regulated by up to 70-fold. A total of 72 and 177 spots showed increased or decreased intensity, respectively, by at least twofold during starvation. The large number of protein spots (1,500) relative to the small genome size (ca. 1.5 Mb) indicates that gene expression may involve co- and posttranslational modifications of proteins. Rates of protein and RNA synthesis were examined throughout the growth phase and up to 7 days of starvation and revealed that synthesis was highly regulated. Rates of protein synthesis and cellular protein content were compared to ribosome content, demonstrating that ribosome synthesis was not directly linked to protein synthesis and that the function of ribosomes may not be limited to translation. By comparing the genetic capacity and physiological responses to starvation of RB2256 to those of the copiotrophic marine bacterium Vibrio angustum S14 (J. Ostling, L. Holmquist, and S. Kjelleberg, J. Bacteriol. 178:4901–4908, 1996), the characteristics of a distinct starvation response were defined for Sphingomonas strain RB2256. The capacity of this ultramicrobacterium to respond to starvation is discussed in terms of the ecological relevance of complete nutrient deprivation in an oligotrophic marine environment. These studies provide the first evidence that marine oligotrophic ultramicrobacteria may be expected to include a starvation response and the capacity for a high degree of gene regulation.