One embodiment of the present invention provides a system that handles instruction fetch requests that return out-of-order at an IFU of a processor. During operation, the system sends a request to obtain a cache line to an instruction cache, wherein the request can be serviced and the cache line can be sent to a fetch buffer before a preceding cache line for a preceding request has returned from the instruction cache. In response to the request, the system receives the cache line from the instruction cache. Next, the system determines whether the cache line was returned out-of-order with respect to the preceding cache line. If so, the system performs an action to handle the out-of-order return.