Abstract: The new video coding standard, H.264 gives a better encoding performance than previous video standards at the cost of expensive computation since it allows motion estimation performing on tri-tree structured macroblock partitioning and multiple reference frames. In this paper, a fast algorithm FIMDA is proposed to accelerate mode decision of inter macroblock. FIMDA makes full use of valuable cues provided by the previous searching reference frames, such as mode, rate distortion cost etc., to eliminate unnecessary modes and reference frames in the following searching. FIMDA can effectively reduce encoding complexity and the quality degradation compared with full search can be ignored. Simulation results show that average complexity reduction exceeds 85% and average quality degradation is only about 0.07dB.