Subsurface bacteria commonly exist in a starvation state with only periodic exposure to utilizable sources of carbon and energy. In this study, the effect of carbon starvation on aerobic toluene degradation was quantitatively evaluated with a selection of bacteria representing all the known toluene oxygenase enzyme pathways. For all the investigated strains, the rate of toluene biodegradation decreased exponentially with starvation time. First-order deactivation rate constants for TMO-expressing bacteria were approximately an order of magnitude greater than those for other oxygenase-expressing bacteria. When growth conditions (the type of growth substrate and the type and concentration of toluene oxygenase inducer) were varied in the cultures prior to the deactivation experiments, the rate of deactivation was not significantly affected, suggesting that the rate of deactivation is independent of previous substrate/inducer conditions. Because TMO-expressing bacteria are known to efficiently detoxify TCE in subsurface environments, these findings have significant implications for in situ TCE bioremediation, specifically for environments experiencing variable growth-substrate exposure conditions.