The low bitt-ate video coding standard H.263 allows four modes of coding, and 31 quantization parameters for each macroblock in a sequence. A new quantization parameter can be set at the beginning of each Group of Block (GOB), and then adapted from macroblock to macroblock within the GC' B in a constrained manner In this work, for every GOB in a frame, an m-best search scheme is employed through a trellis to find the best modes and the best quantizer step changes, in a rate-distortion sense, for both when the starting quantization parameter is predetermined, and when it is; to be selected optimally as well. Thus the algorithm pet forms the most generic kind of optimization at the macroblock level for the P-frames of H.263. It is demonstrated that a relatively low search depth is sufficient to produce coding results superior to established standard-compatible coders.