One embodiment of the present invention provides a system that facilitates a fast execution restart following speculative execution. During normal operation of the system, a processor executes code on a non-speculative mode. Upon encountering a stall condition, the system checkpoints the state of the processor and executes the code in a speculative mode from the point of the stall. As the processor commences execution in speculative mode, it stores copies of instructions as they are issued into a recovery queue. When the stall condition is ultimately resolved, execution in non-speculative mode is recommenced and the execution units are initially loaded with instructions from the recovery queue, thereby avoiding the delay involved in waiting for instructions to propagate through the fetch and the decode stages of the pipeline. At the same time, the processor begins fetching subsequent instructions following the last instruction in the recovery queue. When all the instructions have been loaded from the recovery queue, the execution units begin receiving the subsequent instructions that have propagated through the fetch and decode stages of the pipeline.