With computing demand continuously increasing, data centers in extreme-climate regions typified by the Middle East and North Africa (MENA) face challenges including persistently high cooling energy consumption and a temporal mismatch between computing-driven cooling demand and the availability of natural cooling resources. Considering the regional climatic characteristics of high daytime temperatures and large diurnal temperature swings, a novel thermal management structure integrating phase-change materials (PCM), cooling towers, and heat pumps is proposed. By leveraging the thermal buffering capability of PCM together with the cooling tower’s nighttime natural cooling potential, peak shaving and valley filling for cooling is achieved, which alleviates the temporal mismatch between computing-driven cooling demand and availability of natural cooling resources and increases the natural cooling resources utilization. Furthermore, to coordinate the coupled interactions among transferable computing workloads, electricity pricing, and natural cooling resources in the novel structure, a “computing-electrical-thermal” coordinated optimization model is proposed to reduce electricity cost and optimize the allocation of cooling resources. Since the proposed coordinated optimization model features strong variable coupling and nonlinear characteristics, which cause parameter-propagation delays when conventional hierarchical solution methods are applied, a global solution algorithm is proposed to jointly optimize key variables, including cooling tower power, heat-pump power, and computing workloads migration. Considering a certain data center as a case study, compared with a conventional air–liquid cooling system, electricity consumption is reduced by 17% and the daily operating cost is decreased by USD 2,075 by using the novel thermal management structure. In addition, compared with a conventional electrical–thermal coordination model, the daily operating cost is decreased by USD 556 by using the “computing–electrical–thermal” coordinated optimization model”.