This paper addresses the prevalent issue of label shift in an online setting with missing labels, where data distributions change over time and obtaining timely labels is challenging. While existing methods primarily focus on adjusting or updating the final layer of a pre-trained classifier, we delve into the untapped potential of enhancing feature representations using unlabeled data at test-time. Our novel Online Label Shift adaptation with Online Feature Updates (OLS-OFU) method harnesses self-supervised learning to refine the feature extraction process, thus improving the prediction model. Theoretical analyses confirm that OLS-OFU reduces algorithmic regret by capitalizing on self-supervised learning for feature refinement. Empirical tests on CIFAR-10 and CIFAR-10C datasets, under both online label shift and generalized label shift conditions, underscore OLS-OFU's effectiveness and robustness, especially in cases of domain shifts.