We present a distortion-based approach to packet classification for multimedia transmission over differentiated-services packet networks. Instead of sending all traffic as premium or relying on a priori data partitioning, packets are individually examined and assigned to different service classes depending on the level of distortion that their loss would introduce at the decoder. Applied to video sequences encoded with the ISO MPEG-2 video coding standard, the proposed distortion-based packet marking scheme outperforms source-transparent techniques and provides substantial and consistent gains in PSNR over the regular best-effort case sending as little as 10% of the packets as premium traffic. Video samples are available at http://multimedia.polito.it/icme2001/