Abstract Streams of objects that are associated with one or more labels at the same time appear in many applications. However, stream classi?cation of multi-label data is largely unexplored. Existing approaches try to tackle the problem by transferring traditional single-label stream classi?cation practices to the multi-label domain. Nevertheless, they fail to consider some of the unique properties of the problem such as within and between class imbalance and multiple concept drift. To deal with these challenges, this paper proposes a novel multilabel stream classi?cation approach that employs two windows for each label, one for positive and one for negative examples. Instance-sharing is exploited for space ef?ciency, while a time-ef?cient instantiation based on the k-Nearest Neighbor algorithm is also proposed. Finally, a batch-incremental thresholding technique is proposed to further deal with the class imbalance problem. Results of an empirical comparison against two other methods on three real world datasets are in favor of the proposed approach.