A method and apparatus for color index coding of a block of video data using index prediction based on reconstructed neighboring pixels are disclosed. In one embodiment, color index encoding or decoding is applied to the current pixel indices by deriving index prediction from neighboring pixel indices of the reconstructed neighboring pixels. The reconstructed neighboring pixel values are first transformed into the neighboring pixel indices according to a quantization table to map between major color indices and major color values of the current block. The quantization table can be based on a major color table for the current block or can also be derived at a decoder side. The decoding process may reconstruct the current pixels by converting decoded current pixel indices to reconstructed current pixel values according to the quantization table or by directly copying the reconstructed neighboring pixel values indicated by decoded current pixel indices.