This research proposes a Coding-Gain-Based (CGB) complexity control method for real-time H.264 video encoding in complexity-constrained systems such as wireless handsets. By allocating more complexity to the encoding tools which have higher coding efficiency, the CGB method is able to maximize the overall coding efficiency of the encoder.