Robust streaming of video over wireless networks poses many challenges, as coping with bandwidth variations, data losses, and heterogeneity of the receivers. Rate-distortion (RD) optimization studies are aimed at increasing the reliability of received bitstreams, by selecting the opportunistic system parameters based on the channel conditions and the RD curve. One of the main challenges in the RD optimization is the evaluation of a RD curve. In this work we address the RD curve evaluation issue in cross-layer distortion optimization systems. The tradeoff between approximation in the evaluation and complexity in the computation is investigated. We propose an on-line method able to considerably improve the overall system performance, at the cost of an acceptable increase of the simulation complexity. © 2009 IEEE.