Interdecadal climate variability in an idealized coupled ocean-atmosphere-sea-ice model is studied. The ocean component is a fully three-dimensional primitive equation model and the atmospheric component is a two-dimensional (2D) energy balance model of Budyko-Sellers-North type, while sea ice is represented by a 2D thermodynamic model. In a wide range of parameters the model climatology resembles certain aspects of observed climate. Two types of interdecadal variability are found. The first one is characterized by northward-propagating upper-ocean temperature anomalies in the northwestern part of the ocean basin and a westward-propagating, wavelike temperature pattern at depth. The other type has larger-scale temperature anomalies that propagate westward in both the upper and deep ocean, along the sea ice edge. Both types of oscillations have been found previously in similar models that do not include sea ice. Therefore, the oscillation mechanism does not depend on sea-ice feedbacks nor is it modified very much by the inclusion of sea ice. For some parameter values, the interdecadal oscillations are self-sustained, while for others they are damped. Stochastic-forcing experiments show that, in the latter case, significant interdecadal signals can still be identified in the time series of oceanic heat transport. The periods of these signals, however, do not closely match those identified in a stability analysis of the deterministic model when linearized about its steady state. The authors show that linearization around the actual climatology of the stochastically forced integrations provides a better match for some of the modes that were poorly explained when linearizing about the deterministic model's steady state. The main difference between the two basic states is in the distribution of climatological convective depth, which is affected strongly by intermittent atmospheric forcing.