Abstract Both the positive and negative phases of the North Atlantic Oscillation (NAO+ and NAO−, respectively) and atmospheric blocking in the Euro-Atlantic sector reflect synoptic variability over the region and thus are intrinsically linked. This study examines their relationship from a decadal change perspective. Since the winter-mean NAO index is defined as a time average of instantaneous NAO indices over the whole winter, it is unclear how the activity of European blocking (EB) events can be related to the variation of the positive mean NAO index. Here, this question is examined by dividing the winter period 1978–2011 into two decadal epochs: 1978–94 (P1) with an increasing and high NAO index and 1995–2011 (P2) with a decreasing and low NAO index. Using atmospheric reanalysis data, it is shown that there are more intense and persistent EB events in eastern Europe during P1 than during P2, while the opposite is true for western Europe. It is further shown that there are more NAO+ (NAO−) events during P1 (P2). The EB events associated with NAO+ events extend more eastward and are associated with stronger Atlantic mean zonal wind and weaker western Atlantic storm track during P1 than during P2, but EB events associated with NAO− events increase in western Europe under opposite Atlantic conditions during P2. Thus, the increase in the number of individual NAO+ (NAO−) events results in more EB events in eastern (western) Europe during P1 (P2). The EB change is also associated with the increased frequency of NAO− to NAO+ (NAO+ to NAO−) transition events.