Climate sequences can be applied to defining sensitive climate zones, and then the mining of spatio-temporal teleconnection patts is useful for leing from the past and preparing for the future. However, scale-dependency in this kind of patt is still not well handled by existing work. Therefore, in this study, the multi-scale regionalization is embedded into the spatio-temporal teleconnection patt 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 patts. Experiments on sea surface temperature, sea level pressure, land precipitation and land temperature datasets show that many patts obtained by the multi-scale approach are coincident with prior knowledge, indicating that this method is effective and reasonable. In addition, some unknown teleconnection patts discovered from the multi-scale approach can be further used to guide the prediction of land climate.