This paper addresses the problem of streaming packetized media over a lossy packet network, in a rate-distortion optimized way. Out of all the packets that a sender could transmit at a given transmission opportunity, we show how the sender should compute which packets, if any, to transmit in order to meet an average rate constraint while minimizing the average end-to-end distortion. Experimental results show that our system has steady-state gains of 3–7 dB or more over systems that are not rate-distortion optimized.