The provision of verification for data storage cartridges having data storage tape media employs determining the volume identity of a data storage cartridge; and providing an internal label at each block of data to be written to the data storage tape media of the data storage cartridge, the internal label at least comprising the volume identity. Verification of a label comprises reading an external label of the cartridge, the external label at least comprising a volume identity of the cartridge; determining whether the tape media comprises valid data arranged in blocks; positioning the tape media at one of the data blocks and attempting to read an internal label from the data block; and if so, determining whether the volume identity of the external label matches the volume identity of the internal label, and, if so, determining that the matching volume identity is the volume identity of the cartridge.