The vast, deep, volatile-ice-filled basin informally named Sputnik Planum is central to Plutos geological activity[1,2]. Composed of molecular nitrogen, methane, and carbon monoxide ices[3], but dominated by N2-ice, this ice layer is organized into cells or polygons, typically ~10-40 km across, that resemble the surface manifestation of solid state convection[1,2]. Here we report, based on available rheological measurements[4], that solid layers of N2 ice approximately greater than 1 km thick should convect for estimated present-day heat flow conditions on Pluto. More importantly, we show numerically that convective overturn in a several-km-thick layer of solid nitrogen can explain the great lateral width of the cells. The temperature dependence of N2-ice viscosity implies that the SP ice layer convects in the so-called sluggish lid regime[5], a unique convective mode heretofore not definitively observed in the Solar System. Average surface horizontal velocities of a few cm/yr imply surface transport or renewal times of ~500,000 years, well under the 10 Myr upper limit crater retention age for Sputnik Planum[2]. Similar convective surface renewal may also occur on other dwarf planets in the Kuiper belt, which may help explain the high albedos of some of them.