Provided are a method, system, and program for translating virtual addresses of memory locations within pages of different sizes. In one embodiment, a translation entry containing a physical address is stored in a data structure table for each page. Each virtual address includes a page virtual address which identifies the translation entry containing the physical address of the page containing the memory location. The virtual address may be translated to a translation entry index using the size of the page containing the memory location.