Mammals evolved in the face of fluctuating food availability. How the immune system adapts to transient nutritional stress remains poorly understood. Here, we show that memory T cells collapsed in secondary lymphoid organs in the context of dietary restriction (DR) but dramatically accumulated within the bone marrow (BM), where they adopted a state associated with energy conservation. This response was coordinated by glucocorticoids and associated with a profound remodeling of the BM compartment, which included an increase in T cell homing factors, erythropoiesis, and adipogenesis. Adipocytes, as well as CXCR4-CXCL12 and S1P-S1P1R interactions, contributed to enhanced T cell accumulation in BM during DR. Memory T cell homing to BM during DR was associated with enhanced protection against infections and tumors. Together, this work uncovers a fundamental host strategy to sustain and optimize immunological memory during nutritional challenges that involved a temporal and spatial reorganization of the memory pool within "safe haven" compartments.