With sophisticated video editing technologies, it is becoming increasingly easy to tamper digital video without leaving visual clues. One of the common tampering operations on video is to remove some frames and then re-encode the resulting video. In this paper, we propose a new method for detecting this type of tampering by exploring the temporal patterns of the block artifacts in video sequences. We show that MPEG compression introduces different block artifacts into various types of frames and that the strength of the block artifacts as a function over time has a regular pattern for a given group of pictures (GOP) structure. When some frames are removed from an MPEG video file and the file is then recompressed, the block artifacts introduced by the previous compression would remain and affect the average of block artifact strength of the recompressed one in such a way that depends on the number of deleted frames and the type of GOP used previously. We propose a feature curve to reveal the compression history of an MPEG video file with a given GOP structure, and use it as evidence to detect tampering. Experimental results evaluated on common video benchmark clips demonstrate the effectiveness of the proposed method.