Browsing video on mobile devices such as smartphones and PDAs requires new interface designs and interaction concepts because of their small screen sizes. In this paper, we present four different interfaces which enable users to skim video at different replay speed levels: An interface supporting flicking similar to text browsing on an iPhone™, an elastic slider, and two variations which also allow for interactive speed manipulation. Based on a heuristic evaluation with all four designs, revised versions of the two most promising ones have been implemented. A comparative user study proved the usefulness of the proposed designs. Both interfaces showed the same performance (measured in time needed to solve typical browsing tasks) but achieved different results in subjective user assessments.