Provided are a method, system, removable storage cartridge, and article of manufacture for validating an encryption key file on a removable storage media. Copies of an encryption key file are written to multiple locations on a removable storage media, wherein data is encrypted and decrypted using an encryption key included in the encryption key file. A validation operation is performed on the copy of the encryption key file at one of the key locations, wherein the key locations comprise the locations on the removable storage media to which the encryption key files were written. In response to the copy of the encryption key file not validating, a command is sent to cause the data and valid copies of the encryption key file to be rewritten to a new storage media.