An electronic key storage device including an openable and closable door and a plurality of key holders includes a storage unit configured to store key information of an electronic key usable for each registered user and location information of the key holder matching the electronic key, a user authentication unit configured to perform user authentication by receiving user authentication information so that the door is openable or closable, and a control unit configured to control a fastening operation of the key holder to put the electronic key in the key holder and take the electronic key out of the key holder.