The three-step search (TSS) scheme has been widely used in block-based motion estimation and has also been incorporated into several motion estimation methods successfully to improve their performance. Instead of adopting the conventional square search pattern used in the TSS scheme, this paper presents a new prediction- and affine transformation-based TSS (PATSS) scheme and it leads to a more efficient search pattern. When employing our proposed PATSS scheme into some existing well-known motion estimation algorithms, such as the newly published E3SS algorithm by Jing and Chau, experimental results show that not only the image quality can be improved, but the number of search points can be reduced significantly.