Techniques to prelink software to improve memory de-duplication in a virtual system are described. An apparatus may comprise a processor circuit, a memory unit coupled to the processor circuit to store private memory pages for multiple virtual machines, and a dynamic linker application operative on the processor circuit to link a binary version of a software program with associated program modules at run-time of the binary version on a virtual machine. The dynamic linker application may comprise a master prelink component operative on the processor circuit to relocate a first set of program modules for a first binary version of the software program for a first virtual machine using a first set of virtual memory addresses from a first private memory page allocated to the first virtual machine, and store relocation information for the first set of program modules in a global prelink layout map for use by a second virtual machine. Other embodiments are described and claimed.