A data volume can be created on a network-accessible storage device in a data center for use by a virtual machine instance. More specifically, a management system of the data center may request storage servers to allocate space for the data volume. Prior to receiving confirmation that the data volume has been created, the management system may further request the storage servers to establish a lease that authorizes the virtual machine access to the data volume.