Mechanisms are provided for allowing a streaming server to efficiently provide frames associated with a media stream to a client device. A streaming server receives multiple media streams and determines which frames in the multiple media streams are key frames. When a connection request is received from a client device, a key frame is selected and provided to the client device. A client device receiving a key frame does not have to drop any predictive frames prior to playing a media stream.