This paper presents a spatio-temporal graph-based method of detecting and tracking moving objects by treating the encoded blocks with non-zero motion vectors and/or non-zero residues as potential parts of objects in H. 264/AVC bitstreams. A spatio-temporal graph is constructed by first clustering the encoded blocks of potential object parts into block groups, each of which is defined as an attributed subgraphwhere the attributes of the vertices represent the positions, motion vectors and residues of the blocks. In order to remove false-positive blocks and to track the real objects, temporal connections between subgraphs in two consecutive frames are constructed and the similarities between subgraphs are computed, which constitutes a spatio-temporal graph. We show the experimental results that the proposed spatio-temporal graph-based representation of potential object blocks enables effective detection for the small-sized objects and the objects with small motion vectors and residues, and allows for reliable tracking of the detected objects even under occlusion. The identification of the detected moving objects is determined as rectangular regions of interest (ROIs) for which the ROI sizes and positions are adaptively adjusted to give the best approximation of the real shapes and positions of the objects.