Systems and methods for batched storage hinting with fast guest storage allocation. An example method may involve: detecting, by a hypervisor, that storage has been released by a guest operating system and remains allocated to a virtual machine executing the guest operating system; accessing, by the hypervisor, one or more sets of storage blocks, wherein a set of the one or more sets comprises an identifier associated with the storage and is associated with the virtual machine; receiving, by a processing device executing the hypervisor, a request to allocate a storage block to the virtual machine; identifying, by the hypervisor, at least one storage block of the one or more sets that is associated with the virtual machine; and allocating the at least one storage block to the virtual machine.