An encoder may implement an indexed color history that stores color values for previously encoded pixels. The encoder may obtain a current pixel or current group of pixels for encoding and determine whether to encode the current pixel using the indexed color history. In doing so, the encoder may compare a color value of the current pixel with color values of the previously coded pixels to determine whether the current pixel is sufficiently similar to a previously coded pixel color value, e.g., by satisfying one or more similarity criteria. When the similarity criteria are satisfied, the encoder may encode the current pixel as an index value referencing the entry in the indexed color history storing a color value that satisfies the similarity criteria. When the similarity criteria are not satisfied, the encoder may encode the current pixel using another encoding method or technique.