Climate extremes are intensifying globally, yet their most consequential impacts emerge from temporal clustering and regime persistence rather than isolated events. Here, we demonstrate that climate change systematically restructures extreme-event memory (i.e., the time-dependent influence of past extremes on future hydroclimatic states) across Africa. We develop an event-conditioned probabilities framework and apply it to observations (1985-2024) and climate model projections (2041-2080). We reveal that the dominant 6-month memory timescale strengthens in semi-arid regions but weakens in humid tropics, creating opposing regional responses in hydroclimatic predictability. We found that climate change induces asymmetric regime shifts, making dry states more persistent while wet states more transient. These shifts bias the hydroclimatic regime toward more prolonged droughts. The projected hydroclimatic changes remain robust across emission scenarios, indicating restructuring that is independent of mitigation ambitions. Our findings show that climate change not only makes extreme events more intense but also fundamentally alters how climate systems retain memory of past events. These results have important implications for planning and forecasting in an increasingly uncertain climate.