The disclosed systems and methods enable a virtual machine, including any applications executing thereon, to quickly start executing and servicing users based on pre-staged data blocks supplied from a backup copy in secondary storage. Substantially concurrently with the ongoing execution of the virtual machine, a virtual-machine-file-relocation operation may move data blocks originating in the backup copy to a primary storage destination that becomes the virtual machine's primary data store after the relocation operation completes. An enhanced data agent, operating in conjunction with an enhanced media agent in a storage management system, coordinates restoring of the virtual machine and the launch of the relocation operation. The enhanced media agent may pre-stage certain backed up data blocks which may be needed to launch the virtual machine, based on predictive analysis pertaining to the virtual machine's operational profile. The enhanced media agent may also pre-stage backed up data blocks for the relocation operation, based on the operation's relocation scheme. Servicing read requests to the virtual machine may take priority over ongoing pre-staging of backed up data. Read requests may be tracked so that the media agent may properly maintain the contents of an associated read cache. Some embodiments of the illustrative storage management system may lack, or may simply not require, the relocation operation, and may operate in a “live mount” configuration.