Leakage power consists of an increasing portion of the total power consumption for modern IC designs. Due to the strong inter-dependency between leakage and temperature, it becomes imperative to consider the thermal effects while optimizing the leakage power. In this paper we present a temperaturedependent optimization methodology for on-chip caches. By integrating fast yet accurate coupled thermal-leakage simulations into an optimization flow, we are able to optimally tradeoff between the cache performance and leakage power while considering realistic on-chip temperature distribution. Our analysis indicates that for future memory intensive designs, the lack of chip temperature information can cause a significant error in the leakage power estimation, thus leading to non-optimal cache designs. Our results further imply that the optimization of cache performance and leakage power shall be attacked as part of the whole system design task in which chip-level floorplanning and its thermal impacts are fully addressed.