Conventional authentication methods, proposed mainly for gray-scale and color images, are not appropriate for palette images, which usually contain simple contents with a limited number of colors. In this paper, a new approach is proposed to verify the integrity of palette images and to locate tampered regions without re-quantization and re-indexing processes. The proposed approach is based on a combined use of both the fragile watermarking and the digital signature approaches, taking the advantages of both approaches and avoiding their drawbacks. To protect a block of an image, authentication signals are first generated according to a secret key. Based on an embeddability property defined in the study, the pixels of each block are classified as embeddable or non-embeddable. Only the former ones are used to embed the authentication signals. A corresponding digital signature is generated as well to compensate the possibly limited embedding capacity of the embeddable pixels that are insufficient in number. To authenticate a block, the recovered authentication signals, yielded from the extracted watermark and the received digital signature, are compared with the one generated according to the correct secret key, to prove the block's legitimacy. The effectiveness and the security of the proposed method are analyzed and tested with a variety of palette images. The results indicate that the proposed method can offer high authentication accuracy as well as maintain a good tradeoff between the authentication signal portability and the resulting image quality.