A compressed video playback system which eliminates playback mode transition artifacts. Transitions between various playback modes are effected in such a manner that transition artifacts are eliminated by delaying playback mode transitions until appropriate frames of data are detected for propagation to the compressed video decoder. In addition, compressed video data retrieval methods are improved for supporting multi-speed playback modes in both forward and reverse directions in an optimal manner.