This paper describes a novel and fast approach to Full Search Block Matching (FSBM) employing prediction of search region, based on the sampled statistics of Sum-of-Absolute Difference (SAD) distributions. The motion vector is predicted to belong to either of two regions, representing long-motion and short-motion, with limited amount of overlap between the two. The proposed prediction is statistically validated with more than 98% successes for different video sequences. Experimental results reveal that the proposed Predicted FSBM (PFSBM) algorithm saves up to 89% of computations, as compared to FSBM and the estimation accuracy is very close to that of FSBM. Its performance has been compared with three-step search (TSS) and FSBM for different standard video sequences.