Hydrometeorological patterns can be defined as meaningful and nontrivial associations between hydrological and meteorological parameters over a region. Discovering hydrometeorological patterns is important for many applications, including forecasting hydrometeorological hazards (floods and droughts), predicting the hydrological responses of ungauged basins, and filling in missing hydrological or meteorological records. However, discovering these patterns is challenging due to the special characteristics of hydrological and meteorological data, and is computationally complex due to the archival history of the datasets. Moreover, defining monotonic interest measures to quantify these patterns is difficult. In this study, we propose a new monotonic interest measure, called the hydrometeorological prevalence index, and a novel algorithm for mining hydrometeorological patterns (HMP-Miner) out of large hydrological and meteorological datasets. Experimental evaluations using real datasets show that our proposed algorithm outperforms the naive alternative in discovering hydrometeorological patterns efficiently.