In this paper, we propose a novel and fast face detection algorithm for detecting face in color video sequences. This algorithm can be integrated into a real-time surveillance or a video retrieval or indexing system. We focus on both speed and accuracy in the design of the algorithm. A set of multi-resolution Haar wavelet coefficients pairs is selected by the proposed learning algorithm to determine if a particular region is a face. We apply an ID3-like balanced decision tree for the wavelet coefficients quantization, to reduce the quantization error. For each pairs of quantized features, we estimate the associated conditional joint probability density function from a large set of face and non-face training data. Then, we compute the Kullback Leibler (KL) distance to measure the discrimination between the face and non-face conditional density functions for each feature pair. The feature pairs with larger KL-distance are selected as the feature candidates. It is an effective feature dimension reduction method and helps to speedup the Adaboost training algorithm when considering the spatial relationship between all coefficient pairs. Aided by an automatic skin color judgment method and a Gaussian face location model both in tepmporal and spatial domain, the experiments show that the proposed algorithm runs faster than 4 times the video rate with good detection accuracy.