Tools and techniques for dynamically transcoding media streams are described herein. These tools may provide machine-readable storage media that contain machine-readable instructions that, when executed by the machine, cause the machine to define initial transcoding schemes under which media streams are to be transcoded as they passes between endpoints. In response to changes in conditions affecting the media streams, the machine may dynamically update the initial transcoding scheme.