The urban heat island effect is especially significant in semi-arid climates, generating a myriad of problems for large urban areas. Green space can mitigate warming, providing cooling benefits important to reducing energy consumption and improving human health. The arrangement of green space to reap the full potential of cooling benefits is a challenge, especially considering the diurnal variations of urban heat island effects. Surprisingly, methods that support the strategic placement of green space in the context of urban heat island are lacking. Integrating geographic information systems, remote sensing, spatial statistics and spatial optimization, we developed a framework to identify the best locations and configuration of new green space with respect to cooling benefits. The developed multi-objective model is applied to evaluate the diurnal cooling trade-offs in Phoenix, Arizona. As a result of optimal green space placement, significant cooling potentials can be achieved. A reduction of land surface temperature of approximately 1–2 °C locally and 0.5 °C regionally can be achieved by the addition of new green space. 96% of potential day and night cooling benefits can be achieved through simultaneous consideration. The results also demonstrate that clustered green space enhances local cooling because of the agglomeration effect; whereas, dispersed patterns lead to greater overall regional cooling. The optimization based framework can effectively inform planning decisions with regard to green space allocation to best ameliorate excessive heat.