This paper presents a fast algorithm for H.264 fractional ME. Motivated by the highly correlation of cost between neighboring fractional pel position, the proposed algorithm efficiently explores the neighborhood position around the minimum one and thus skips other unlikely ones. Thus, the proposed algorithm can complete the search by only examining 8 or 9 search points instead of 17 search points in the search algorithm of reference software. Early termination technique is applied in every single search point. The simulation result shows that the proposed algorithm can reduce about 50% of computation complexity compared to that in reference software but only with 0.1-0.2 dB PSNR degradation and less than 2% of bit rate increase.