A solution is provided to estimate motion vectors of a video. A multistage motion vector prediction engine is configured to estimate multiple best block-matching motion vectors for each block in each video frame of the video. For each stage of the motion vector estimation for a block of a video frame, the prediction engine selects a test vector form a predictor set of test vectors, computes a rate-distortion optimization (RDO) based metric for the selected test vector, and selects a subset of test vectors as individual best matched motion vectors based on the RDO based metric. The selected individual best matched motion vectors are compared and a total best matched motion vector is selected based on the comparison. The prediction engine selects iteratively applies one or more global matching criteria to the selected best matched motion vector to select a best matched motion vector for the block of pixels.