The emerging H.264 advanced video coding (H.264/AVC) standard achieves significant improvement in coding efficiency compared with previous standards such as MPEG-2 and H.263. One major contribution of its gain profits from variable-block-size motion estimation, which also leads to higher computational complexity. In this paper, we propose a fast predictive variable-block-size motion estimation algorithm for H.264/AVC. The algorithm takes advantage of three effective predictive schemes-stationary block prediction, predictive search for non-stationary blocks and predictive multi-pattern refinement search in merging process. Experimental results and comparative analysis have shown that our proposed algorithm can reduce the computational complexity up to about 2% of fast full search motion estimation algorithm, with negligible average PSNR loss of 0.065 dB and bit rate increase of 2.43%.