Systems and methods for smooth rewind playback of streamed media are provided. The media includes relatively-encoded frames and independently-encoded frames. The method includes receiving a rewind request indicating a rewind speed for rewind playback of the media, selectively dropping relatively-encoded frame(s) based on a receipt constraint and a decoding constraint to form a subset of the media, and receiving frames of the subset. The method further includes selecting, in a reverse order, a selected group of pictures (GOP) included within the subset, and decoding relatively-encoded frame(s) of the GOP in a forward sequential frame order. The method further includes caching relatively-encoded frame(s) of the GOP in the forward sequential frame order, and when caching, dropping and overwriting relatively-encoded frame(s) of the GOP selectively according to a memory constraint and/or a display constraint. The method further includes displaying relatively-encoded frame(s) of the GOP in a reverse sequential frame order.