In this paper, a novel reversible data hiding scheme with color replacement is proposed to embed the palette information of a palette image into its corresponding grayscale image. Two different qualities of images can be provided with the proposed scheme. They are the marked grayscale image and the original palette image, one for free access, and another for limited access, respectively. The proposed method reordered the palette colors of the image according to their occurrence frequencies and then repeated performing a palette color replacement procedure to embed the palette information into the grayscale image. Consequentially, we can reconstruct the palette image by extracting the embedded information from the marked grayscale image. The performance of the proposed method is demonstrated by showing the good qualities of both the marked and the rebuilt images.