A video encoder and method of video encoding are provided. At an encoding stage a selected degree of quantization is applied to the encoding of macroblocks of the input video sequence and quantized part-encoded macroblocks are generated. Quantization circuitry in the encoding stage is configured to select the selected degree of quantization for each macroblock in a current slice in dependence on a complexity estimate indicative of the expected entropy encoding complexity of a predetermined set of the quantized part-encoded macroblocks defined for that macroblock.