Uploads of restored virtual machine (“VM”) data to cloud storage, e.g., VM restore-to-cloud operations, are performed without having to write whole restored virtual disk files to a proxy server before the virtual disk data begins uploading to cloud. Restored data blocks from a backup source are locally cached, staged for efficiency, and asynchronously uploaded to the cloud page-by-page without tapping mass storage resources on the proxy. Downloads of VM data from cloud storage, e.g., VM backup-from-cloud, are performed without having to download a virtual disk file in its entirety to the proxy server before the backup operation begins generating a backup copy. This speeds up “pulling” VM data from the cloud by pre-fetching and locally caching downloaded data blocks. The cached data blocks are processed for backup and stored page-by-page directly into a secondary copy of the cloud VM virtual-disk file without tapping mass storage resource at the proxy.