Watermarking is a potential method for copyright protection and authentication of multimedia data on the Internet. The watermarking process can be viewed as a communication task, where the watermark, acting like information, is embedded into a host image, acting like noise, in a communication channel that is susceptible to all kinds of attacks, acting like jamming. In this paper, a novel watermarking scheme using frequency-shift keying (FSK) modulation with high-variance block selection is proposed to achieve superior performance in robustness and imperceptibility. In the proposed scheme, a secret bit is embedded into two rather than one DCT coefficient of a block. This is analogous to the FSK as opposed to the amplitude-shift keying (ASK) modulation in digital communication. High-variance block selection (HVBS) is employed to enhance robustness. In order to solve the synchronization problem caused by HVBS, local block selection and a novel technique called the two-state constraint is implemented. In order to demonstrate the effectness of the proposed scheme, simulations under various conditions were conducted. The empirical results show that our proposed scheme can sustain most common attacks, including JPEG compression, rotating, resizing, cropping, painting, noising, and blurring. A comparison between watermarking with and without HVBS shows that HVBS with the two-state constraint can effectively enhance robustness without the sacrifice of imperceptibility. The enhancement is much more significant for host images with fluctuation characteristics than for those with smooth characteristics. The comparison between ASK and FSK shows that the extracted watermark from the latter deteriorates gracefully and that from the former is blown out as the strength of a JPEG attack rises beyond a threshold. For other common attacks, the ASK and FSK perform about the same except, for the blurring attack, for which the extracted watermark from the latter can be clearly identified while that from the former is blown out.