Ambient seismic noise is characterized by randomness incurred by the random position and strength of the noise sources as well as the heterogeneous properties of the medium through which it propagates. Here we use ambient noise data recorded prior to the 1996 Gjálp eruption in Iceland in order to show that a reduction of noise randomness can be a clear short-term precursor to volcanic activity. The eruption was preceded on 29 September 1996 by a Mw ~5.6 earthquake that occurred in the caldera rim of the Bárdarbunga volcano. A significant reduction of randomness started occurring 8 days before the earthquake and 10 days before the onset of the eruption. This reduction was observed even at stations more than 100 km away from the eruption site. Randomness increased to its previous levels 160 minutes after the Bárdarbunga earthquake, during which time aftershocks migrated from the Bárdarbunga caldera to a site near the Gjálp eruption fissure. We attribute this precursory reduction of randomness to the lack of higher frequencies (>1 Hz) in the noise wavefield caused by high absorption losses as hot magma ascended in the upper crust.