Proxy records represent an invaluable source of information for reconstructing past climatic variations, but they are associated with considerable uncertainties. For a systematic quantification of these reconstruction errors, however, knowledge is required not only of their individual sources but also of their auto-correlation structure as this determines the timescale dependence of their magnitude, an issue that has been often ignored until now. Here a spectral approach to uncertainty analysis is provided for paleoclimate reconstructions obtained from single sediment proxy records. The formulation in the spectral domain rather than the time domain allows for an explicit demonstration and quantification of the timescale dependence that is inherent in any proxy-based reconstruction uncertainty. This study is published in two parts. In this first part, the theoretical concept is presented, and analytic expressions are derived for the power spectral density of the reconstruction error of sediment proxy records. The underlying model takes into account the spectral structure of the climate signal, seasonal and orbital variations, bioturbation, sampling of a finite number of signal carriers, and uncorrelated measurement noise, and it includes the effects of spectral aliasing and leakage. The uncertainty estimation method, based upon this model, is illustrated by simple examples. In the second part of this study, published separately, the method is implemented in an application-oriented context, and more detailed examples are presented.