A system and method for efficiently performing motion estimation during temporal prediction for coding. When a new frame is presented for coding, an encoder may identify a limited number of pixel blocks within the input frame that are complex. The encoder may perform motion estimation searches to find reference frame(s) that are adequate prediction references for the complex pixel blocks. The encoder may search for prediction references for the remaining pixel blocks of the new frame, confining the search to the reference frame(s) that were selected as prediction references of the complex pixel blocks.