Climate variability is critically important for nature and society, especially if it increases in amplitude and/or fluctuations become more persistent. However, the issues of whether climate variability is changing, and if so, whether this is due to anthropogenic forcing, are subjects of ongoing debate. Increases in the amplitude and persistence of temperature fluctuations have been detected in some regions, e.g. the North Pacific, but there is no agreed global signal. Here we systematically scan monthly surface temperature indices and spatial datasets to look for trends in variance and autocorrelation (persistence). We show that monthly temperature variability and autocorrelation increased over 1957-2002 across large parts of the North Pacific, North Atlantic, North America and the Mediterranean. Furthermore, (multi)decadal internal climate variability appears to influence trends in monthly temperature variability and autocorrelation. Historically-forced climate models do not reproduce the observed trends in temperature variance and autocorrelation, consistent with the models poorly capturing (multi)decadal internal climate variability. Based on a review of established spatial correlations and corresponding mechanistic 'teleconnections' we hypothesise that observed slowing down of sea surface temperature variability contributed to observed increases in land temperature variability and autocorrelation, which in turn contributed to persistent droughts in North America and the Mediterranean.