Embodiments of the invention generally provide a method and apparatus for fast motion estimation. One embodiment of a method for motion estimation includes classifying a macroblock of a source frame in accordance with an initial matching cost, an intermediate matching cost, and a final matching cost, where the intermediate matching cost is estimated based on a predicted motion vector for the source frame and the final matching cost is estimated based on a final motion vector for a correlated macroblock in a prior frame, performing motion estimation for the macroblock based upon the classifying, wherein an early termination is applied in accordance with a result of the classifying, and outputting a motion vector for the macroblock based on a result of the motion estimation.