To achieve on-demand software deployment in large-scale virtual machine (VM) environments, this paper presents a prefetch-based on-demand software deployment optimization mechanism to reduce the VM startup latency and to improve the VM running performance at user side. Based on the characteristics of user’s behavior of using software and fine-grained splitting of virtual disk (VD) image, the paper prefetches those small-sized being-used VD images at user side from server side by using an access frequency and priority-based prefetch target recognition algorithm—AFPTR and uses a dynamic adjustment mechanism to adjust the prefetch amount during the prefetching process so as to improve the local hit ratio of virtual disk accessing and then the VM running performance at user side. Based on QEMU virtual machine monitor and Linux system, a prototype is built to implement the prefetch mechanism. Experiments on the prototype show that the prefetch mechanism can effectively reduce the VM startup latency and improve the VM running performance at user side, supporting on-demand, fast software deployment in virtual machine environments.