A virtual tape server for executing a method involving a partitioning of a virtual tape volume into a plurality of virtual tape blocks. The virtual tape volume includes a virtual tape volume header having recovery information, each virtual tape block includes a virtual tape block header identifying the virtual tape volume and a block sequence number, and one or more of the virtual tape blocks includes the virtual tape volume header. The method further involves a formatting of a physical tape volume including each virtual tape block.