Natural archives such as sediments, ice, tree rings or speleothems provide indirect observations of past climate at local and regional scales. In this paper, we provide a computational device to properly make evaluated reconstructions of climate indices using these paleo-data. It provides optimizing cross-validation algorithms and four regression methods that are applied to the reconstruction of the North Atlantic Oscillation index and compared in this study.