We propose synergistic software and hardware mechanisms that alleviate the address translation overhead in virtualized systems. On the software side, we propose contiguity- aware (CA) paging, a novel physical memory allocation technique that creates larger-than-a-page contiguous mappings while preserving the flexibility of demand paging. CA paging is applicable to the hypervisor and guest OS memory manager independently, as well as in native systems. On the hardware side, we propose SpOT, a simple micro-architectural mechanism to hide TLB miss latency by exploiting the regularity of large contiguous mappings to predict address translations. We implement and emulate the proposed techniques for the x86-64 architecture in Linux and KVM, and evaluate them across a variety of memory-intensive workloads. Our results show that: (i) CA paging is highly effective at creating vast contiguous mappings in both native and virtualized scenarios, even when memory is fragmented, and (ii) SpOT exploits the provided contiguity and reduces address translation overhead of nested paging from ~18% to ~1.2%.