Land cover composition and change are important aspects for many scientific research and socioeconomic assessments. The multi-date land cover change detection is generally more difficult and time-consuming to select enough training samples when considering multi-date image labels at the same location. To improve the accuracy for multi-date change detection, this study proposed a new algorithm framework, combining self-learning and relearning algorithm. Wuhan was selected as the experimental area, and Landsat images in 2005 and 2016 were used to extract six main types of change classes. Firstly, PCM (primitive co-occurrence matrix) and the minimum class certainty are used to ensure the high confidence of selected candidate set samples, and then the most informative samples are identified for classification from the candidate samples. To save computing costs, we adopt clustering method to reduce the self-relearning samples. Based on our experimental results, the self-relearning algorithm increases the final classification accuracy by approximately 2.5% (from 92.64% to 95.09%) in the case of using few initial training samples, providing a feasible solution for the multi-date change detection.