Mechanisms are provided for presenting a media location browsing interface to facilitate a media search and/or seek. A client device receives a media stream from a streaming server. This client device provides a media location browsing interface after receiving the media stream. This media location browsing interface includes a plurality of key frames representing locations along the media stream that are selectable at the client device. A seek request to play the media stream from a seek location corresponding to one of the plurality of key frames is captured. The client device begins playback of the media stream at the seek location.