We show that the monthly North Atlantic Oscillation index routinely used in climatology as an indicator for global climate variability is not an optimal choice. A critical Markov analysis of the two pressure time-series for both, monthly and daily NAO index, indicates that the monthly index, due to its low sampling rate, contains higher stochastic terms than the daily index. Applying a recently developed variationally optimized Markov analysis leads to a new NAO index with minimal stochasticity.