Using K-means clustering algorithms, four weather regimes over the North Atlantic-European region are obtained. Moreover, the relationship between the Madden-Julian Oscillation (MJO) in the tropics and the four weather regimes over the North Atlantic-European region is investigated. It is found that the winter mean North Atlantic Oscillation (NAO) index can be characterized by the number of days of NAO events calculated by K-means clustering algorithms. During two periods, 1978-1990 (P1) and 1991-2010 (P2), phase 3 (6) of the MJO leads to a positive (negative) NAO regime. In particular, the MJO is found to be very important for the NAO transition during P1, but unimportant during P2. When the MJO is within the first (sixth) phase during P1, the NAO event can transit from the weak negative (positive) phase to the positive (negative) phase. However, only the transition between dipole and wave train patterns is evident during P2, when the MJO is in the first phase.