Lake surface water temperatures are warming worldwide, raising concerns about the future integrity of valuable lake ecosystem services. In contrast to surface water temperatures, we know far less about what is happening to water temperature beneath the surface, where most organisms live. Moreover, we know little about which characteristics make lakes more or less sensitive to climate change and other environmental stressors. We examined changes in lake thermal structure for 231 lakes across northeastern North America (NENA), a region with an exceptionally high density of lakes. We determined how lake thermal structure has changed in recent decades (1975–2012) and assessed which lake characteristics are related to changes in lake thermal structure. In general, NENA lakes had increasing near-surface temperatures and thermal stratification strength. On average, changes in deepwater temperatures for the 231 lakes were not significantly different than zero, but individually, half of the lakes experienced warming and half cooling deepwater temperature through time. More transparent lakes (Secchi transparency >5 m) tended to have higher near-surface warming and greater increases in strength of thermal stratification than less transparent lakes. Whole-lake warming was greatest in polymictic lakes, where frequent summer mixing distributed heat throughout the water column. Lakes often function as important sentinels of climate change, but lake characteristics within and across regions modify the magnitude of the signal with important implications for lake biology, ecology and chemistry.