What is the fastest way to heat up a system? While the intuitive answer is to couple the system to the highest temperature, we show that this protocol is not always the optimal. We propose a strategy for the construction of exponentially faster heating protocols, which consist of a pre-cooling stage. We discuss the idea behind our strategy in discrete-state systems, and give examples for fast protocols in the three-state system, as well as in the Ising model at the thermodynamic limit.