A watermark coding method and its recording medium utilize image interleaving and wavelet-based transformation to enhance the robustness of the image. The watermark series to be inserted is converted, encrypted, and modulated to increase the difficulty in decoding and restoring. Finally, the watermark is distributed and hidden in various frequency bands of the image in a frequency hopping way, generating a robust watermarked image. When used in a recording medium, side information produced during coding is recorded in the lead-in area of the recording medium to reduce the chances of illegal copying.