Super-resolution (SR) algorithms for video sequences with high resolution (HR) guide frames can provide outstanding performances. Non-local means (NLM) algorithm compares the similarity between a pixel and its neighbors. NLM replaces every pixel with a weighted average of its neighbors. The NLM based SR algorithm can super-resolve low resolution (LR) frames using the HR guide frames in the video sequence. However, the fixed decaying factor of NLM cannot satisfy regions of distinct characteristics in a LR frame. The fixed searching window fails to balance the requirements of low computational complexity and good SR images. Thus, we propose novel criteria for selecting the decaying factor and searching window adaptively. Bilateral adjacent HR frames are used to handle the occlusion problem. The experimental results verify the validity of the proposed method.