In this study, the long-range relationships between North Atlantic Oscillation (NAO) and precipitation data obtained from Climate Prediction Centre (CPC) Merged Analysis of Precipitation (CMAP) from 1979 to 2016 are investigated using Detrended Fluctuation Moving Average Cross-Correlation Analysis (DMCA). In the atmosphere, teleconnections through strong convective processes sporadically affect various climatic regimes in Europe, Mediterranean basin, North Africa, Middle East, and Caucasus. The NAO is one of the teleconnection processes and results in heavy rainfall in the Mediterranean basin during its negative phase while it gives rise to rain in Europe during its positive phase. The DMCA technique shows that the NAO fluctuation series exhibit different long-range cross-correlation coefficients, rho DMCA(s) with "s" being the moving average time window length, between the precipitation values and NAO. Large rho DMCA(s) coefficients with time window(s) larger than 12 months were obtained particularly over the Mediterranean basin, near the North Pole including northern Europe. Furthermore, the rho DMCA(s) coefficients were grouped into clusters using K-mean method to distinguish the similar patterns. The 1st cluster refers to the negative phase of the NAO indicating warm-rainy conditions and dry spells, which is especially evident in the Mediterranean basin. The 2nd cluster represents the long-range cross-correlation with respect to the positive phase of NAO and precipitation values, particularly for the Western and Northern Europe. Conversely, the 3rd cluster is evaluated as power law of long-range cross-correlations between the precipitation and NAO with respect to the different time scale processes.