A pipelining decoding apparatus and method, and a computer-readable recording medium for storing a computer program for controlling the pipelining decoding apparatus. Pixel values of each of the recovered images corresponding to previous macroblocks are stored as neighboring pixel values. Motion is predicted in a picture corresponding to a current macro block using the stored neighboring pixel values. An original image is recovered from the current macroblock using the result of the prediction of the motion in the picture and residue information. Some of the pixel values of the recovered image corresponding to the current macroblock are stored and the recovered image is deblocking-filtered.