A method and device for tracking error propagation and refreshing a video stream is provided. The proposed subject matter comprises of an error propagation tracking method that works in the sub-sampled domain to reduce computational cycles and memory bandwidth. Further, the tracking based update of the error propagation metric is done differently for static and non-static regions to avoid unnecessary refresh of static areas. Through suitable thresholding of the metric at a macroblock (MB) level, a set of refresh MBs are selected for each frame. These refresh MBs are coded either as an intra MB or as an inter MB that is predicted from one or more reliable reference frames (—frames that are known to be available at the decoder with negligible errors—). Such inter coding of refresh MBs improves the compression efficiency when compared to pure intra coding of refresh MBs. Further, variants to the threshold selection are presented that result in temporally uniform distribution of the number of refresh MBs and a strict refresh scheme wherein all MBs are guaranteed to be with negligible errors following a packet loss within a committed refresh period. In addition, to using the error propagation metric, spatial connectivity to already chosen refresh MBs is used in the selection of additional refresh MBs within a frame and across frames; this reduces the rate of error propagation due to part of a macroblock predicting from older, erroneous neighboring MBs and in turn requiring more refresh MBs on the average per frame.