Most video rate-control research emphasizes constant bit-rate (CBR) applications. These aim to produce a CBR bitstream with the highest possible quality, within the bitrate constraint and with no consideration for quality variation. In this paper, two MPEG-4 Constant-Quality (CQ) CBR controls are proposed. These aim to produce a CBR bitstream that meets a target quality level whenever possible. The Frame-level Laplacian CQ (FLCQ) algorithm uses a distortion model based on a Laplacian model for DCT coefficients. In contrast, the MB-level Viterbi CQ (MVCQ) algorithm uses the Viterbi algorithm to determine the best combination of MB-QP’s. “CQ” is measured by the deviation of the mean quality from the target quality, and by quality variance over time. Simulation results suggest that the proposed algorithms perform better than Q2 and TM5 under these measures. In some cases, they produce bitstreams with fewer bits while having higher average PSNR, and smaller variance. The FLCQ algorithm has more variation in quality than the MVCQ algorithm. With extra computational complexity, the MVCQ algorithm gives the best performance over all algorithms tested. Often, it precisely meets the target PSNR with no variation. This is truly a CQ rate-control algorithm.