Reconstructed daily mean sea level pressure patterns of the North Atlantic-European region are classified for the period 1850 to 2003 to explore long-term changes of the atmospheric circulation and its impact on long-term temperature variability in the central European region. Commonly used k-means clustering algorithms resulted in classifications of low quality because of methodological deficiencies leading to local optima by chance for complex datasets. In contrast, a newly implemented clustering scheme combining the concepts of simulated annealing and diversified randomization (SANDRA) is able to reduce substantially the influence of chance in the cluster assignment, leading to partitions that are noticeably nearer to the global optimum and more stable. The differences between conventional cluster analysis and the SANDRA scheme are significant for subsequent analyses of single clusters - in particular, for trend analysis. Conventional indices used to determine the appropriate number of clusters failed to provide clear guidance, indicating that no distinct separation between clusters of circulation types exists in the dataset. Therefore, the number of clusters is determined by an external indicator, the so-called dominance criteria for t-mode principal component analysis. Nevertheless, the resulting partitions are stable for certain numbers of clusters and provide meaningful and reproducible clusters. The resulting types of pressure patterns reveal pronounced long-term variability and various significant trends of the time series of seasonal cluster frequency. Tentative estimations of central European temperature changes based solely on seasonal cluster frequencies can explain between 33.9% (summer) and 59.0% (winter) of temperature variance on the seasonal time scale. However, the signs of long-term changes in temperature are correctly reproduced even on multidecadal-centennial time scales. Moreover, linear warming trends are reproduced, implying from one-third up to one-half of the observed temperature increase between 1851/52 and 2003 (except for summer, but with significant trends for spring and autumn), indicating that changes in daily circulation patterns contribute to the observed overall long-term warming in the central European region.