Climate sequences can be applied to defining sensitive climate zones, and then the mining of spatio-temporal teleconnection patterns is useful for learning from the past and preparing for the future. However, scale-dependency in this kind of pattern is still not well handled by existing work. Therefore, in this study, the multi-scale regionalization is embedded into the spatio-temporal teleconnection pattern mining between anomalous sea and land climatic events. A modified scale-space clustering algorithm is first developed to group climate sequences into multi-scale climate zones. Then, scale variance analysis method is employed to identify climate zones at characteristic scales, indicating the main characteristics of geographical phenomena. Finally,by using the climate zones identified at characteristic scales, a time association rule mining algorithm based on sliding time windows is employed to discover spatio-temporal teleconnection patterns. Experiments on sea surface temperature, sea level pressure, land precipitation and land temperature datasets show that many patterns obtained by the multi-scale approach are coincident with prior knowledge, indicating that this method is effective and reasonable. In addition, some unknown teleconnection patterns discovered from the multi-scale approach can be further used to guide the prediction of land climate.