Video databases and their corresponding evaluation protocols are used to compare classifiers, such as face detection an tracking. In this paper, a six level evaluation protocol for the Damascened XM2VTS (DXM2VTS) database is presented to measure face detection and tracking performance. Additionally, a novel database containing thousands of videos is created by combining video from the XM2VTS database with a set of newly recorded standardized real-life video used as background and with several realistic degradations, such as motion blur, noise, etc. Moreover, two publicly available and published face detection algorithms, are tested on the six suggested difficulty levels of the protocol. Their performance on video in terms of false acceptance, false rejection, correct detection, and repeatability, are reported and conclusions are drawn.