The North Atlantic Oscillation (NAO) index plays a crucial role in the climatic evolution of the Northern Hemisphere. Predicting NAO evolution is very challenging due to the large number of physical processes that influence it. Quantitative surveys have tried to detect possible long-term trends or periodic features in the NAO evolution. In this study, we implement a stochastic model that is able to replicate the statistical characteristics of the NAO index, based on a non-homogeneous semi-Markov Model. For this purpose, we set up two states of the process, namely positive and negative NAO values. We also analyse positive and negative sequences of NAO values. The model characteristics are estimated using daily real values during the period 1950-2013 and we lastly implement a Monte Carlo procedure in order to simulate daily NAO values covering a 1-year time horizon. Next, this model is compared with a typical ARMA-GARCH model used in time series analysis, which appears to be underperforming, in contrast with the semi-Markov one.