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 short-term GCR flux changes 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 (GCM) experiment is used to test the causal relationship of the observed cloud changes to the detected SLAT anomalies. Results indicate that the anomalous cloud changes were responsible for producing the observed SLAT changes, implying that if there is a causal relationship between significant decreases in the rate of GCR flux (~0.79 GU, where GU denotes a change of 1% of the 11-year solar cycle amplitude in four days) and decreases in cloud cover (~1.9 CU, where CU denotes a change of 1% cloud cover in four days), an increase in SLAT (~0.05 KU, where KU denotes a temperature change of 1 K in four days) can be expected. The influence of GCRs is clearly distinguishable from changes in solar irradiance and the interplanetary magnetic field. However, the results of the GCM experiment are found to be somewhat limited by the ability of the model to successfully reproduce observed cloud cover. These results provide perhaps the most compelling evidence presented thus far of a GCR-climate relationship. From this analysis we conclude that a GCR-climate relationship is governed by both short-term GCR changes and internal atmospheric precursor conditions.