Conditional proteolysis is a crucial process regulating the abundance of key regulatory proteins associated with the cell cycle, differentiation pathways, or cellular response to abiotic stress in eukaryotic and prokaryotic organisms. We provide evidence that conditional proteolysis is involved in the rapid and dramatic reduction in abundance of the cyanobacterial RNA helicase, CrhR, in response to a temperature upshift from 20 to 30°C. The proteolytic activity is not a general protein degradation response, since proteolysis is only present and/or functional in cells grown at 30°C and is only transiently active at 30°C. Degradation is also autoregulatory, since the CrhR proteolytic target is required for activation of the degradation machinery. This suggests that an autoregulatory feedback loop exists in which the target of the proteolytic machinery, CrhR, is required for activation of the system. Inhibition of translation revealed that only elongation is required for induction of the temperature-regulated proteolysis, suggesting that translation of an activating factor was already initiated at 20°C. The results indicate that Synechocystis responds to a temperature shift via two independent pathways: a CrhR-independent sensing and signal transduction pathway that regulates induction of crhR expression at low temperature and a CrhR-dependent conditional proteolytic pathway at elevated temperature. The data link the potential for CrhR RNA helicase alteration of RNA secondary structure with the autoregulatory induction of conditional proteolysis in the response of Synechocystis to temperature upshift.