In this paper, a fast and efficient method for selecting the encoding modes and the quantizers for the ITU H.263 standard is presented. H.263 is a very low bit rate video coder which produces satisfactory results at bit rates around 24 kbits/second for low motion quarter common intermediate format (QCIF) color sequences such as 'mother and daughter.' Two major target applications for H.263 are video telephony using public switched telephone network lines and video telephony over wireless channels. In both cases, the channel bandwidth is very small, hence the efficiency of the video coder needs to be as high as possible. The presented algorithm addresses this problem by finding the smallest frame distortion for a given frame bit budget. The presented scheme is based on Lagrangian relaxation and dynamic programming (DP). It employs a fast evaluation of the operational rate distortion curve in the DCT domain and a fast iterative search which is based on a Bezier function.