In this paper, we propose a novel tree-structured multi-view face detector (MVFD), which adopts the coarse-to-fine strategy to divide the entire face space into smaller and smaller subspaces. For this purpose, a newly extended boosting algorithm named Vector Boosting is developed to train the predictors for the branching nodes of the tree that have multi-components outputs as vectors. Our MVFD covers a large range of the face space, say, +/- 45° rotation in plane (RIP) and +/- 90° rotation off plane (ROP), and achieves high accuracy and amazing speed (about 40 ms per frame on a 320 × 240 video sequence) compared with previous published works. As a result, by simply rotating the detector 90°, 180° and 270°, a rotation invariant (360° RIP) MVFD is implemented that achieves real time performance (11 fps on a 320 × 240 video sequence) with high accuracy.