The increasing computational complexity of label propagation-based facial image annotation when applied on multimedia data whose cardinality increases over the time (e.g., when analyzing video or movie content on-line), can be reduced by using an incremental approach. In this paper, a method for incremental label propagation on facial images is described. The similarity matrix is incrementally constructed by employing the kd-tree nearest neighbor algorithm. Furthermore, the matrix inversion, which is included in the label propagation solution, is calculated with a block-wise inversion formula involving the Woodbury matrix identity. Experiments show significant computational savings when the incremental approach is applied on a dataset of three full length movies. Moreover, the classification accuracy was improved in most cases.