An apparatus and method for color buffer compression. For example, one embodiment of a method comprises: specifying a palette of available colors within a color space to be used for quantizing color values of pixels within a tile; subdividing the color space into a plurality of axis-aligned bucket regions, each of the available colors falling within one of the bucket regions; and quantizing the color values based on both the palette of available colors and the axis-aligned bucket regions.