The effect of the Galactic Cosmic Ray (GCR) flux on Earth's climate is highly uncertain. Using a novel sampling approach based around observing periods of significant cloud changes, a statistically robust relationship is identified between the rate of GCR flux and the most rapid mid-latitude (60°-30° N/S) cloud decreases operating over daily timescales; this signal is verified in surface level air temperature (SLAT) reanalysis data. A General Circulation Model experiment is used to test the causal relationship of the observed cloud changes to the detected SLAT anomalies. Results indicate that the cloud anomalies were responsible for producing the observed SLAT changes, implying a link between significant decreases in the rate of GCR flux (~0.79%/day (relative to the peak-to-peak amplitude of 11-yr solar cycle)), decreases in cloud cover (~1.9%/day) and increases in SLAT (~0.05 K/day). The influence of GCRs is clearly distinguishable from changes in solar irradiance and the interplanetary magnetic field. These results provide the most compelling evidence presented thus far of a GCR-climate relationship. From this analysis we conclude: (i) a GCR-climate relationship is governed by both the rate of GCR flux and internal precursor conditions; and (ii) it is likely that this natural forcing has not contributed significantly to recent anthropogenic temperature rises.