The H.264/AVC standard, jointly developed by the ITU-T and MPEG committees, is becoming prevalent in video industry . It achieves its high coding efficiency by employing a number of advances in video coding technology. The H.264/AVC encoder 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 initial QP is decided on from 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. First, after calculating the variance of the vertical pixels of the first frame, the complexity level is decided based on the variance of the vertical pixels. The prediction equation is selected using the complexity level of input video sequences. Finally, the optimal initial QP is obtained based on the target bitrate. Experimental results and analysis show that the proposed scheme has significantly increased the average PSNR, reduced the variation of bit count level, and improved the perpetual quality of the reconstructed video.