In this paper, we study the interdependencies between system's leakage and on-chip temperature. We show that the temperature variation caused by on-chip heat accumulation has a large impact in estimating the system's leakage energy. More importantly, we propose an online temperature-aware leakage minimization technique to demonstrate how to incorporate the temperature information to reduce energy consumption at real time. The basic idea is to run when the system is cool and the workload is high and to put the system to sleep when it is hot and the workload is light. The online algorithm has low run-time complexity and achieves significant leakage energy saving. In fact, we are able to get about 25% leakage reduction on both real life and artificial benchmarks. Comparing to our optimal offline algorithm, the above online algorithm provides similar energy savings with similar decisions on how to put the system to sleep and how to wake it up. Finally, our temperature-aware leakage minimization techniques can be combined with existing DVS methods to improve the total energy efficiency by further saving on leakage.