Protein quality control (proteostasis) depends on constant protein degradation and resynthesis, and is essential for proper homeostasis in systems from single cells to whole organisms. Cells possess several mechanisms and processes to maintain proteostasis. At one end of the spectrum, the heat shock proteins modulate protein folding and repair. At the other end, the proteasome and autophagy as well as other lysosome-dependent systems, function in the degradation of dysfunctional proteins. In this review, we examine how these systems interact to maintain proteostasis. Both the direct cellular data on heat shock control over autophagy and the time course of exercise-associated changes in humans support the model that heat shock response and autophagy are tightly linked. Studying the links between exercise stress and molecular control of proteostasis provides evidence that the heat shock response and autophagy coordinate and undergo sequential activation and downregulation, and that this is essential for proper proteostasis in eukaryotic systems.