Provided are a method, system, and article of manufacture for rekeying encryption keys for removable storage media. A rekey request is received for a coupled removable storage media, wherein encryption on the coupled removable storage media uses a first key and wherein the rekey request indicates a second key. The first key and the second key are accessed in response to the rekey request. The first key is used to perform decryption for the coupled removable storage media and the second key is used to perform encryption for the coupled removable storage media.