The public-key encryption of quantum messages (PKQE) serves as a quantum version of the public-key encryption, in which both plaintexts and ciphertexts are quantum states and both the public-key and the secret key are classical strings. In this work, we initiate the study on the quantum public-key encryption of quantum messages (qPKQE), a variant of PKQE, in which the quantum messages are encrypted with the quantum public-key and the ciphertexts are decrypted with the classical secret key. We introduce different-level security notions for qPKQE, proposing generic constructions to achieve these security notions, and ultimately provide the first construction of qPKQE based on the quantum-secure one-way functions (OWF), proving the existence of qPKQE is implied by that of OWF. To show the necessity of the study, we also prove that no statistical-secure qPKQE exist. As a byproduct of our exploration, we propose the notion of the quantum key-encapsulation mechanism (qKEM), which may be of independent interest in the quantum cryptography theory.