Merkle Cryptosystem (MC) is the first cryptosystem which introduces general concept of the public key cryptography. In this paper, we propose Improved Merkle Cryptosystem (IMC), which has significant security advantages over both MC and a variant of MC (VMC). In IMC, cryptographic hash functions and a new puzzle structure are used together in order to increase the security of MC and VMC. The key agreement value, which is send as clear text in VMC, is hidden using cryptographic hash function in IMC. Also, in order to increase security of the key agreement value, auxiliary keys are used. Notice that, in IMC, computational advantages of VMC remain unchanged while its security is increased. Utilizing computational advantages of VMC, IMC has also security and storage advantages over original MC. It is shown that, with these improvements, IMC can provide as high security as some well-known public key cryptosystems while MC and VMC can not provide same security due to performance problems.