Very rapid changes in temperature and ocean circulation are known to take place during ice age cycles of the last million years. These changes are believed to be triggered by the rapid collapse of ice sheets bordering the North Atlantic Ocean. We investigated here when these changes first began, by reconstructing very detailed records of ocean surface temperature off the Portuguese margin, where these millennial-scale events are well documented for the recent past. We found that the first abrupt changes in temperature began at ~2.72 Ma, the same time that North Atlantic Ocean sediments record the first outbreak of icebergs into the open ocean in the region. Since ice sheets ringing the North Atlantic were quite small at this time, our data imply that ocean circulation is extremely sensitive to modest collapses in ice sheets in the region.