Long-term climate variations have the potential to amplify or dampen (human-induced) trends in temperature. Understanding natural climate variability is therefore of vital importance, especially since the variability itself may change with a changing climate. Here, we quantify the magnitude and other characteristics of interannual to decadal variability in Arctic temperature and their dependence on the climate state. Moreover, we identify the processes responsible for the state dependency of the variations, using five quasi-equilibrium climate simulations of a state-of-the-art global climate model with 0.25, 0.5, 1, 2, and 4 times present-day atmospheric CO2 forcing. The natural fluctuations in Arctic temperature, including their dependence on the state of the climate, are linked to anomalous atmospheric and oceanic heat transports toward the Arctic. Model results suggest that atmospheric heat transport leads (and also controls) Arctic temperature variations on interannual time scales, whereas oceanic transport is found to govern the fluctuations on decadal time scales. This time-scale transition of atmospheric to oceanic dominance for Arctic temperature variations is most obvious when there is interannual to decadal variability in Arctic sea ice cover. In warm climates (without Arctic sea ice cover), there is no correlation between oceanic transport and surface air temperature on any time scale. In cold climates (with full Arctic sea ice cover), interaction between ocean and atmosphere is limited, leaving poleward atmospheric heat transport to be the primary driver on all time scales (interannual and decadal).