To improve video quality and coding efficiency, H.264/AVC adopted an adaptive rate control. But this method has a problem as it cannot predict an accurate quantization parameter (QP) for the first frame. The first QP is decided among four constant values by using encoder input parameters. It does not consider encoding bits, results in significant fluctuation of the image quality and decreases the average quality of the whole coded sequence. In this paper, we propose a new algorithm for the first frame QP decision in the H.264/AVC encoder. The QP is decided by the existing algorithm and the first frame is encoded. According to the encoded bits, the new initial QP is decided. We can predict optimal value because there is a linear relationship between encoded bits and the new initial QP. Next, we re-encode the first frame using the new initial QP. Experimental results show that the proposed algorithm not only achieves better quality than the state of the art algorithm, but also adopts a rate control for the sequence that was impossible with the existing algorithm. By reducing fluctuation, subjective quality also improved. Copyright 2007 ICST.