Provided are a computer program product, system and method for a redundant key server encryption environment. A key server receives from at least one remote key server public keys associated with the at least one remote key server. The key server receives a request for an encryption key from a requesting device and generates the encryption key for use by the requesting device to unlock a storage. The key server generates a first wrapped encryption key by encrypting the encryption key with a requesting device public key, a second wrapped encryption key by encrypting the encryption key with a public key associated with the key server, and at least one additional wrapped encryption key by encrypting the encryption key with the at least one public key provided by the at least one remote key server. The key server transmits the generated keys to the requesting device.