Diverse stresses including starvation and muscle disuse cause skeletal muscle atrophy. However, the molecular mechanisms of muscle atrophy are complex and not well understood. Here, we demonstrate that growth arrest and DNA damage-inducible 45a protein (Gadd45a) is a critical mediator of muscle atrophy. We identified Gadd45a through an unbiased search for potential downstream mediators of the stress-inducible, pro-atrophy transcription factor ATF4. We show that Gadd45a is required for skeletal muscle atrophy induced by three distinct skeletal muscle stresses: fasting, muscle immobilization, and muscle denervation. Conversely, forced expression of Gadd45a in muscle or cultured myotubes induces atrophy in the absence of upstream stress. We show that muscle-specific ATF4 knock-out mice have a reduced capacity to induce Gadd45a mRNA in response to stress, and as a result, they undergo less atrophy in response to fasting or muscle immobilization. Interestingly, Gadd45a is a myonuclear protein that induces myonuclear remodeling and a comprehensive program for muscle atrophy. Gadd45a represses genes involved in anabolic signaling and energy production, and it induces pro-atrophy genes. As a result, Gadd45a reduces multiple barriers to muscle atrophy (including PGC-1α, Akt activity, and protein synthesis) and stimulates pro-atrophy mechanisms (including autophagy and caspase-mediated proteolysis). These results elucidate a critical stress-induced pathway that reprograms muscle gene expression to cause atrophy.