Instrumental records of mean annual temperature extend back to the seventeenth and eighteenth centuries at multiple sites in Europe. For such long time series, we expect and find that histograms of mean annual temperature data become skewed toward higher temperatures with time because of global warming. However, we also find that skewness changed abruptly and started increasing between 1985 and 1991 (95% confidence) at 17 sites. We argue that this finding may imply an abrupt change in the climate system affecting Europe which probably occurred at this time. We investigate possible causes and find Arctic sea ice loss, potentially linked to reduced sulfate aerosol emissions and coupled to temperature by an albedo feedback mechanism, a likely candidate. This is based on good correlations of sea ice extent and sulfate aerosol emissions with skewness of mean annual temperature data.