This paper presents a distortion optimized streaming algorithm for on-demand streaming of multimedia. Given the pre-encoded packets of a multimedia stream, we propose an algorithm for selecting an appropriate subset of these packets such that the overall client distortion is minimized. This minimization is performed within the rate constraints imposed by the communication channel. In the interest of computation it is desirable to limit the horizon (i.e. the look-ahead) over which the optimization is performed. Inevitably, shortening the horizon leads to sub-optimal results. We alleviate the impact due to this through the introduction of a buffering constraint that stipulates a minimum desired buffer occupancy at all time during the streaming session. We pose this problem as a Lagrangian minimization – the solution to which is obtained through an iterative descent algorithm. We demonstrate the efficacy of the proposed approach through empirical evaluation.