The successive elimination algorithm (SEA) has already proved successful in block motion estimation. This paper presents a simple and efficient algorithm called the threshold-based SEA as a search engine to take advantage of the simplicity of the SEA while avoiding its redundant computation. In addition, the threshold-based SEA utilizes a threshold adaptation mechanism to efficiently distribute the available computational power of the employed codec to blocks of video sequences. Since the threshold-based approach is performed at each search candidate block, it can be combined not only with the SEA but also with other fast algorithms, including the three-step search, the block-based gradient descent search, and the diamond search. Depending on the motion activity in the sequences, experimental results indicate that the threshold-based approach can uniformly achieve a quality improvement over the original SEA for the same computation.