In this study, we present a denoising algorithm for high-frame-rate videos in an ultra-low illumination environment on the basis of Kalman filtering model and a new motion segmentation scheme. The Kalman filter removes temporal noise from signals by propagating error covariance statistics. Regarded as the process noise for imaging, motion is important in Kalman filtering. We propose a new motion estimation scheme that is suitable for serious noise. This scheme employs the small motion vector characteristic of high-frame-rate videos. Small changing patches are intentionally neglected because distinguishing details from large-scale noise is difficult and unimportant. Finally, a spatial bilateral filter is used to improve denoising capability in the motion area. Experiments are performed on videos with both synthetic and real noises. Results show that the proposed algorithm outperforms other state-of-the-art methods in both peak signal-to-noise ratio objective evaluation and visual quality.