In a practical video encoder, a video sequence obtained from a CCD camera inevitably conveys noise, which degrades not only image quality but also coding efficiency. Based on the statistic analysis of noise signal,a noise variance adaptive two-stage successive elimination algorithm(NVA-SEA) for block motion estimation is presented. Simulation results demonstrate that the proposed algorithm can get close performance to the full search, while the computation time has been significantly reduced.