A mechanism for generating pre-translated segments for use in virtual to real address translation is provided in which segments that are determined to meet a density threshold are promoted to a pre-translated segment class. The pages of these segments are moved to a contiguous portion of memory and the segment table entry corresponding to the segment is updated to indicate the segment to be a pre-translated segment and to include the base real address for the contiguous portion of memory. In one embodiment, as each page is moved, its page table entry is updated to point to the new location of the page so that the page is still accessible during promotion of the segment to a pre-translated segment. In this way, virtual-to-real address translation may be performed by concatenating the segment base real address, the page identifier, and a byte offset into the page.