A fast and reliable spatio-temporal algorithm for estimating additive white Gaussian noise (AWGN) in video sequences is proposed. The input video is divided into right cuboids. Estimations are made on three independent domains (spatial, temporal-horizontal, and temporal-vertical). Inside each domain, homogeneous blocks are first identified based on Sobel gradients with an adaptive and self-determined threshold. The selected blocks are then filtered by a Laplacian operator. The average of the filtering convolutions provides the estimated noise variance for each domain. The arithmetic average of these three estimated variances is computed to be the final estimated noise variance. Experimental results show that the proposed algorithm achieves better performance and maintains low complexity for a variety of video sequences over a large range of noise variances.