An experiment of 1750-yr duration has been performed with a three-dimensional coupled atmosphere-sea-ice-ocean-vegetation model to study the transient effect of global deforestation on climate. The response consists of two phases. First, the initial global cooling due to increased surface albedo (forest replaced by grassland) is enhanced by a significant expansion of the sea-ice cover in both hemispheres, which increases the surface albedo further. Second, a non-linear response of the ocean thermohaline circulation results in a southward shift of the main deep-convection site and reduced northward heat transport in the Atlantic Ocean, leading to enhanced global cooling due to a further expansion of Arctic sea ice. Ultimately, surface temperatures over northwestern North America become sufficiently low to prevent the snow pack to melt in summer. Our results thus suggest that large-scale changes in forest cover may lead to non-linear changes in the climate system.