Commutative encryption and watermarking (CEW) is an emerging method that combines encryption technology with digital watermarking technology, which has double protection capabilities to achieve secure transmission and copyright tracking. In the field of multimedia data security, this method has been extensively used. However, existing algorithms have not considered the sensitivity and specificity of high-resolution remote sensing (HRRS) images; thus, they cannot completely protect HRRS images. This study proposes a CEW algorithm based on homomorphic encryption to solve this problem. First, partitioning is performed on the original image, and then integer wavelet transform is used to extract low- and high-frequency coefficients. Finally, the Paillier algorithm encrypts the low- and high-frequency coefficients of each sub-block, and the watermark is embedded in the low-frequency coefficient. The experimental results show that the proposed algorithm can achieve commutativity between encryption and watermarking and reconstruct the plaintext and ciphertext data’s watermark. In addition, the proposed algorithm has high encryption security and strong watermark robustness.