In this paper we present a novel method to detect and track moving objects in H.264/AVC bitstreams by processing motion vector and residue information. The encoded blocks with nonzero motion vectors and residues are first detected as moving object candidates. A spatio-temporal graph in video sequences is then constructed to represent groups of blocks in each frame and their associations to the other groups of blocks in subsequent frames. Identification and refinement of ROIs for moving objects being tracked are done by graph matching and adaptive ROI-size adjustment. The experimental results show that the proposed method can correctly identify real moving objects from frame to frame and can effectively detect small-sized objects and objects with small motion vectors and residues, as well as by recognizing moving objects even under occlusion.