In this paper, we investigate the large-scale multi-label image classification problem when images with unknown novel classes come in stream during the training stage. It coincides with the practical requirement that usually novel classes are detected and used to update an existing image recognition system. Most existing multi-label image classification methods cannot be directly applied in this scenario, where the training and testing stages must have the same label set. In this paper, we proposed to learn a multi-label classifier and a novel-class detector alternately to solve this problem. The multi-label classifier is learned using a convolutional neural network (CNN) from the images in the known classes. We proposed a recurrent novel-class detector which is learned in the supervised manner to detect the novel class by encoding image features with the multi-label information. In the experiment, our method is evaluated on several large-scale multi-label benchmarks including MS COCO. The results show the proposed method is comparable to most existing multi-label image classification methods, which validate its efficacy when encountering streaming images with unknown classes.