Systems and methods for variable block size early termination for video coding are described. In one aspect a set of thresholds are selected based on block sizes in a video encoding scheme. The thresholds include a respective threshold for each block size used by the encoding scheme. For each macroblock of multiple macroblocks in a video data sequence, blocks in the macroblock are evaluated in view of respective threshold(s) to determine if motion estimation operations can be terminated prior to evaluating remaining blocks in the macroblock.