A method of seeking within a time shift buffer includes receiving a media stream from a remotely located media source over a network, and generating a time shift buffer associated with the media stream. The time shift buffer includes a number of frames with keyframes provided at a certain intervals. When a seek request associated with a desired time within the media stream is received, the system determines a nearest keyframe within the set of keyframes that is previous to and closest in time to the desired time, displays the nearest keyframe, then considers in turn each of the frames subsequent to the nearest keyframe until a desired frame corresponding to the desired time is reached displayed. The system cancels the previous examining step and determines a new nearest keyframe in the event a second seek request is received.