A translation lookaside buffer is described for use with a microprocessor capable of speculative and out-of-order processing of memory instructions. The translation lookaside buffer is non-blocking in response to translation lookaside buffer misses requiring page table walks. Once a translation lookaside buffer miss is detected, a page table walk is initiated to satisfy the miss. During the page table walk, additional memory instructions are processed by the translation lookaside buffer. Any additional instructions which cause translation lookaside buffer hits are merely processed by the translation lookaside buffer. However, instructions causing translation lookaside buffer misses while the page table walk is being performed are blocked pending completion of the page table walk. Once the page table walk is completed the blocked instructions are reawakened and are again processed by the translation lookaside buffer. Global and selective wakeup mechanisms are described. An implementation wherein the non-blocking translation lookaside buffer is provided within a microprocessor capable of speculative and out-of-order processing is also described.