In this paper, we propose a novel self-recovery scheme for tampered images using vector quantization (VQ) indexing and image inpainting. Cover image blocks are classified into complex blocks and smooth blocks according to the distribution characteristics. Due to the good performance of the compressed representation of VQ and the automatic repairing capability of image inpainting, the recovery-bits of each cover block are generated by its VQ index and the inpainting indicator. Recovery-bits and authentication-bits are embedded into the LSB planes of the cover image to produce the watermarked image. On the receiver side, after tampered blocks are all localized, the extracted recovery-bits are used to judge the classification of each tampered block. By analyzing the validity of the VQ indices and the damaged degree of the neighboring regions, the adaptive recovery mechanism can be utilized to restore all the tampered blocks by using VQ index and image inpainting. Experimental results demonstrate the effectiveness of the proposed scheme.