Systems and methods for fast storage allocation for encrypted storage are disclosed. An example method may include receiving, by a processing device executing an operating system, an identification of a first storage block that has been released by a first virtual machine; tracking, by the operating system, an encryption status corresponding to the first storage block to indicate whether the first storage block contains encrypted content; receiving a request to allocate storage to a second virtual machine; analyzing, by the operating system, the first storage block to determine that the first storage block contains encrypted content in view of the encryption status corresponding the first storage block; and allocating the first storage block containing the encrypted content to the second virtual machine without clearing the encrypted content of the first storage block.