A method and apparatus for decoding video data that is encoded by bit rate control to keep a bandwidth of a bit stream in a predetermined range are provided. The encoded video data is decoded, picture quality estimation information is estimated, the estimation including information about a bit stream size of a decoded video frame, the number of fragmented macro blocks included in the video frame, and the number of skip-mode macro blocks included in the video frame, the picture quality of the video data is determined based on a correlation between picture quality estimation information and SNR, and the video data is output by applying a picture quality improving algorithm to the video data, if the determined picture quality is lower than a predetermined level.