Sleep stage classification is critical for diagnosing sleep quality. While deep neural networks are becoming popular for automatic sleep stage classification with supervised learning, large-scale labeled datasets are still hard to acquire. Recently, self-supervised learning (SSL) has become one of the most prominent approaches to alleviate the burden of labeling works. However, existing SSL methods are mainly designed for non-temporally correlated data and only learning representations from an instance level. Hence, the objective of this paper is to learn robust and generalizable representations for physiological signals with self-supervised learning. Specifically, we make the following contributions: (1) we propose a novel co-training scheme by exploiting complementary information from multiple views (time view and frequency view) of physiological signals to mine more positive samples, which overcomes the drawback of popular InfoNCE and achieves semantic-level representation learning; (2) we extend our framework with a memory module, implemented by a queue and a moving-averaged encoder, to enlarge the pool of negative candidates and keep the up-to-date representation; (3) extensive experiments conducted on sleep stage classification demonstrate state-of-the-art performance compared with SSL baselines, achieving 71.6% and 57.9% accuracies on two sleep datasets, SleepEDF and ISRUC respectively. The code is publicly available at https://github.com/larryshaw0079/CoSleep .