Three existing cold season North Atlantic Oscillation (NAO) indices which were reconstructed from proxy data were assessed for their consistency and robustness at the interannual and decadal timescales. All three indices were found to be inconsistent with an observed NAO index, whereas two other, mainly instrumentally based indices, showed good agreement with observations. The combination of the proxy-based indices into one new index by means of multivariate regression yielded some improvement, such that the skill of the new index was comparable or higher than the individual indices. However, the new index still did not correlate significantly with the instrumentally based reference time series prior to 1850. Our results suggest non-stationarities in the statistical relationships between the proxy-based indices and the NAO. This has important implications with regard to the choice of verification periods and predictor data-base for upcoming reconstruction attempts. ¿ 2000 American Geophysical Union