Spatio-temporal subpixel mapping (STSPM) has shown great potential for monitoring land surfaces, by generating land cover maps with both fine spatial and temporal resolutions. Selecting cloud-free fine spatial resolution images as ancillary data for STSPM can ensure that the temporal dependence term is measured for all subpixels, as in all current STSPM methods. However, such images are generally limited by cloud contamination, thereby resulting in great land cover changes between the available clear image and the desired fine spatial resolution land cover map. This research proposes a cloud-independent STSPM (C-STSPM) method to reconstruct the fine spatial resolution land cover maps by using cloudy images directly, which are assumed to have fewer land cover changes than temporally distant clear images. Cloud-independent spatio-temporal dependence was proposed in the presence of cloudy pixels. Experiments were performed under various cloud conditions involving 21 × 21 pairs of simulated cloudy images. The results demonstrate that by utilizing land cover information of clear pixels in cloudy images, more accurate prediction can be produced by C-STSPM compared to directly discarding those cloudy images, even if the number of cloud pixels increases to 95%. The advantage of C-STSPM is more evident when the clouds are distributed sparsely, which benefits from the increased number of clear pixels at the edge of the cloudy areas. Furthermore, a negative linear correlation was detected between the prediction accuracy and the ratio of overlapping cloudy pixels in the cloudy images. Moreover, the C-STSPM method helps to deal with abrupt changes occurred in the temporally distant cloud-free images by utilizing the temporally adjacent cloudy images with gradual land cover changes. Overall, the C-STSPM method provides a completely new solution to make fuller use of the widely existing cloudy images in multi-scale time-series images.