A method and apparatus to maximize video slice size is described herein. The method packs as many macroblocks as possible within a capped-size slice, while preserving user-defined quality constraints. The probability to conform to the maximum slice size constraint may be adjusted according to a user-defined parameter. The method may be integrated into a rate control process of a video encoder. The method predicts whether encoding a macroblock with a quantization parameter exceeds a current slice size constraint. It further predicts whether encoding a given number of macroblocks with a given configuration of quantization parameters exceeds the current slice size constraint. The method then proceeds to encode the current macroblock either on a condition that encoding the given number of macroblocks with the given configuration of quantization parameters falls below the size constraint of the current slice or after determining that a new slice is needed.