Adapting to distribution changes is a critical challenge in modern machine learning. Due to streaming nature of data, the data is usually unlabeled and naturally have continuously distribution change. To this end, we investigate the problem of sequentially adapting the model to non-stationary environments, where the data distribution is continuously shifting and only a few unlabeled data are available each time. Continual test-time adaptation methods have shown promising results in reliable pseudo label generation, while still lack exploration of representation learning in non-stationary environments. In this paper, we propose using non-stationary representation learning to adaptively align the unlabeled data stream with changing distributions to the source data representation, by leveraging a sketch of source labeled data. To alleviate the data scarcity in non-stationary representation learning, we propose a novel two-layer adaptive learning algorithm, Ada-ReAlign, that uses a group of base learner to explore varying lengths of the unlabeled data stream and adaptively combined with a meta learner to deal with the unknown and continuously changing data distribution with theoretical guarantees. Experiments on both benchmark datasets and a real-world application validate the effectiveness of our proposed algorithm and the adaptive representation alignment mechanism.