Cloud covers, which are generally present in optical remote sensing images, limit the usage of acquired images and increase the difficulty in data analysis. Thus, information reconstruction of cloud-contaminated images generally plays an important role in image analysis. This paper proposes a novel method to reconstruct cloud-contaminated information in multitemporal remote sensing images. Based on the concept of utilizing temporal correlation of multitemporal images, we propose a patch-based information reconstruction algorithm that spatiotemporally segments a sequence of images into clusters containing several spatially connected components called patches and then clones information from cloud-free and high-similarity patches to their corresponding cloud-contaminated patches. In addition, a seam that passes through homogenous regions is used in information reconstruction to reduce radiometric inconsistency, and information cloning is solved using an optimization process with the determined seam. These processes enable the proposed method to well reconstruct missing information. Qualitative analyses of image sequences acquired by a Landsat-7 Enhanced Thematic Mapper Plus (ETM+) sensor and a quantitative analysis of simulated data with various cloud contamination conditions are conducted to evaluate the proposed method. The experimental results demonstrate the superiority of the proposed method to related methods in terms of radiometric accuracy and consistency, particularly for large clouds in a heterogeneous landscape.