An apparatus downloads files of encoded video including interspersed key frames over a communication network. The apparatus plays back video from the downloaded files and creates a trick play index based on the downloaded files. The trick play index indicates network locations of the key frames in the encoded video files. When the apparatus receives a trick play request, such as rewind or fast forward, the client device downloads the key frames from the indicated network locations, and plays back video from the downloaded key frames.