Several fragile watermarking techniques cannot detect vector quantization (VQ) attacks; the block-based approach, for example. Celik et al. proposed a hierarchical watermarking approach to reveal the VQ attacks. In order to improve the hierarchical watermarking approach, we present a new fragile watermarking technique based on genetic algorithms (GAs) to embed watermarks into the frequency domain of a host image. Different from existing schemes, the adjustment in the host image by GAs will achieve the embedding of fragile watermarks. The technique can provide a fundamental platform for other fragile watermarking techniques. Furthermore, the embedding of watermarks into frequency domain enhances the security in fragile watermarking.