An essential part of the cellular response to environmental stress is a reversible translational suppression, taking place in dynamic cytoplasmic structures called stress granules (SGs). We discovered that HDAC6, a cytoplasmic deacetylase that acts on tubulin and HSP90 and also binds ubiquitinated proteins with high affinity, is a novel critical SG component. We found that HDAC6 interacts with another SG protein, G3BP (Ras-GTPase-activating protein SH3 domain-binding protein 1), and localizes to SGs under all stress conditions tested. We show that pharmacological inhibition or genetic ablation of HDAC6 abolishes SG formation. Intriguingly, we found that the ubiquitin-binding domain of HDAC6 is essential and that SGs are strongly positive for ubiquitin. Moreover, disruption of microtubule arrays or impairment of motor proteins also prevents formation of SGs. These findings identify HDAC6 as a central component of the stress response, and suggest that it coordinates the formation of SGs by mediating the motor-protein-driven movement of individual SG components along microtubules.