A “media stream customizer” customizes buffered media streams by inserting one or more media objects into the stream to maintain an approximate buffer level. Specifically, when media objects such as songs, jingles, advertisements, etc., are deleted from the buffered stream (based on some user specified preferences), the buffer level will decrease. Therefore, over time, as more objects are deleted, the amount of the media stream being buffered continues to decrease, thereby limiting the ability to perform additional deletions from the stream. To address this limitation, the media stream customizer automatically chooses one or more media objects to insert back into the stream, and ensures that the inserted objects are consistent with any surrounding content of the media stream, thereby maintaining an approximate buffer level. In addition, the buffered content can also be stretched using pitch preserving audio stretching techniques to further compensate for deletions from the buffered stream.