This paper researches the problem of Continuous Top-k Skyline Pairs Query (TKSPQ for short) over data stream, an important problem in the field of streaming data management. Let \(\mathcal {S}\) be the set of streaming data. Each TKSPQ, denoted as q(n, s, k), monitors q(n) objects within the window. When q(s) objects update, q returns q(k) pairs with the highest \(pair\, score\) in skyline pair set. To the best of our knowledge, it is the first effort to support TKSPQ over data stream. In this paper, we propose a novel framework named PSPS (short for Partition-based Skyline Pair Search) over data stream. We partition objects within the window into a set of partitions, and then select a group of high-quality pairs within each partition as candidate pairs. Then, we introduce a novel index called PQ-Tree to organize objects, which helps us efficiently select high-quality pairs. Finally, we propose a set of novel algorithms for supporting incremental maintenance when handling newly arrived/expired objects. Extensive experiments on both real and synthetic datasets demonstrate that PSPS effectively supports TKSPQ over data stream.