The real-time generation of key frames in a media data stream is disclosed. One embodiment provides a method of processing encoded media data comprising receiving a request to play back the encoded media data from a media receiver, generating one or more key frames from the encoded media data, and sending the generated key frame or key frames to the media receiver. The key frames are generated by decoding the media data, and then encoding the key frames from the decoded media data. In this manner, a frequency of key frames in a media data stream may be increased to improve trick mode and 1.times. playback.