A video decoder system receives a user request for non-linear decoding of at least one video frame from a video stream encoded using an Intra macroblock refresh process. The request includes a first frame offset corresponding to a user requested first decoding frame within the video stream for commencing the non-linear decoding. The decoder system: determines an Intra-refresh period corresponding to at least one encoded Predictive frame in the video stream during which all macroblocks in the user requested first decoding frame are Intra encoded at least once; determines a second frame offset as a function of the Intra-refresh period and the user requested first frame offset, the second frame offset corresponding to a second decoding frame within the video stream. Finally, the decoder system decodes the video stream starting at the second decoding frame and suppresses the display of the video stream until the first decoding frame.