This study proposes a novel reversible data-hiding method based on an iterative approach for palette-based images. In each iteration, the number of occurrences of palette color in the image is computed in order to identify the most and least frequently occurring colors in a palette for data hiding. Data are hidden by sacrificing the least frequent color and placing the most frequent color in its position in the palette to make a pair. After the most frequent color takes over the palette index of the least frequent color, two palette indices stand for the most frequent color. Therefore, one bit can be hidden in every pixel where the most frequent color occurs in the image. To make the host image reversible, the overhead information caused by sacrificing the least frequent color must be saved for image reconstruction. The performance of the proposed method is demonstrated on test images by showing the capacity and distortion. Several successful similar efforts have also been implemented for comparison. Experimental results indicate that the proposed method has a high embedding capacity and good marked-image quality.