Systems and methods for batched storage hinting with fast guest storage allocation. An example method may involve: receiving, by a processing device executing a hypervisor, an indication of a plurality of storage blocks that have been released by a guest operating system and remain allocated to a virtual machine executing the guest operating system; adding, by the hypervisor, identifiers of the plurality of storage blocks to a set of storage block identifiers, wherein an identifier in the set is associated with the virtual machine; receiving a request to allocate storage to the virtual machine; analyzing, by the hypervisor, the set of storage block identifiers to identify a storage block associated with the virtual machine; and allocating the identified storage block to the virtual machine.