We use a coupled energy-balance/glacier-flow model to reconstruct Holocene climate from a 5000-yr record of glacier length fluctuations at Sólheimajökull, an outlet glacier in southern Iceland. The climatic reconstruction is presented in terms of Equilibrium-Line Altitude and is translated to envelopes of possible temperature and precipitation changes. The reconstruction is highly resolved between AD 1700 and 1990: the 20th Century retreat of the glacier resulted from a warming between AD 1920 and 1940 while the advance since AD 1970 was in response to both a cooling and a precipitation increase after AD 1940. The early 18th Century climate of Iceland was warm, comparable to that of the early 20th Century, while the coldest period in recent history occurred during the 1780s. Earlier Holocene glacier advances at about 5000, 3100 and 1400 yr BP, and in the 10th and 14th Centuries AD resulted from cooling of 1-2°C, and correlate with worldwide glacier expansion, atmospheric changes in Greenland and changes in ocean circulation north of Iceland. Glacier expansions follow periods when sea ice is extensive in the Greenland and Barents Sea. Resulting temperature changes mean that natural climatic variability has a large signature in Iceland, making it difficult to isolate any longer term trends, such as an enhanced anthropogenic signal.