We have used a numerical model of bottom-heated, two-dimensional convection in boxes of aspect ratios 2.5 and 4.0 to study the differences in time-dependent convection between Newtonian and stress-dependent viscosity. The onset of time dependence due to boundary layer instability is found at approximately the same effective Rayleigh number for both rheologies. However, with increasing Rayleigh number the temporal and spatial fluctuations in the flow field become much more pronounced with non-Newtonian rheology; also, the tendency for breakup of long cells into smaller ones is stronger. The presence of stress-dependent rheology can cause long-wavelength lateral viscosity variations up to an order of magnitude; this result could have strong implications for the interpretation of mantle viscosity from postglacial rebound. ¿ American Geophysical Union 1989