The normalised difference vegetation index (NDVI) is a useful tool for studying vegetation activity and ecosystem performance at a large spatial scale. In this study we use the Gravity Recovery and Climate Experiment (GRACE) total water storage (TWS) estimates to examine temporal variability of the NDVI across Australia. We aim to demonstrate a new method that reveals the moisture dependence of vegetation cover at different temporal resolutions. Time series of monthly GRACE TWS anomalies are decomposed into different temporal frequencies using a discrete wavelet transform and analysed against time series of the NDVI anomalies in a stepwise regression. The results show that combinations of different frequencies of decomposed GRACE TWS data explain NDVI temporal variations better than raw GRACE TWS alone. Generally, the NDVI appears to be more sensitive to interannual changes in water storage than shorter changes, though grassland-dominated areas are sensitive to higher-frequencies of water-storage changes. Different types of vegetation, defined by areas of land use type, show distinct differences in how they respond to the changes in water storage, which is generally consistent with our physical understanding. This unique method provides useful insight into how the NDVI is affected by changes in water storage at different temporal scales across land use types.