Techniques are described to allow substation of blocks into a virtual machine image of an executing virtual machine. A patch may be applied to a first virtual machine image. One or more blocks modified by the patch are identified and copied to a host having a virtual machine executing from a virtual machine image that is based on the first virtual machine image (prior to the patch). While the virtual machine is executing, the substitution blocks are applied (supersede) corresponding original blocks in the virtual machine image. A guest operating system in the virtual machine may either begin using an executable file in a substitution block. In addition, the guest operating system may be forced to flush from memory and cache executable code replaced by the substitution block.