An apparatus has a queue, each entry stores a different line of a stream of instruction bytes and accumulated prefix information associated with each instruction byte. Control logic: (a) detects a condition where an initial portion of an instruction partially within a first line stored in the bottom entry (BE) of the queue remains unextracted from the queue, wherein the initial portion instruction bytes are all prefix bytes; (b) saves away the initial portion length, shifts the first line in the BE out of the queue, and shifts a second line into the BE, in response to detecting the condition; (c) extracts instruction bytes of the unextracted instruction from the second line in the BE and extracts accumulated prefix information from the second line of the BE in place of the already shifted out initial portion prefix bytes; (d) calculates the unextracted instruction length using the saved length; and (e) extracts an instruction other than the unextracted instruction from the second line in the BE using the calculated length.