This paper presents the concept of Rate-Distortion Hint Track (RDHT), and evaluates two specific implementations of streaming systems that employ RDHT. Characteristics of a compressed media source that are often difficult to compute in realtime but crucial to general online optimized streaming algorithms are precomputed and stored in a RDHT. In such a way, low-complexity streaming can be realized for systems that adapt to variations in transport conditions such as bandwidth or packet loss. An RDHT-based streaming system has three components: (1) an R-D Hint Track, (2) an algorithm for using the RDHT to predict the distortion for different packet schedules, and (3) a method for determining the best packet schedule. Two RDHT-based systems are presented which perform R-D optimized scheduling with dramatically reduced complexity as compared to conventional on-line R-D optimized streaming algorithms. Experimental results demonstrate that for the difficult case of R-D optimized scheduling of non-scalably coded video (H.264, I-frame followed by all P-frames), the proposed systems provide 7-12 dB gain when adapting to a bandwidth constraint and 2-4 dB gain when adapting to random packet loss, both relative to a conventional streaming system that does not take into account the different importance of individual packets. Furthermore, the proposed RDHT-based systems achieve this R-D optimized performance with a complexity comparable to that of the conventional non R-D optimized streaming system.