Northern Hemisphere surface temperature reconstructions suggest that the late twentieth century was warmer than any other time during the past 500 years and possibly any time during the past 1,300 years (refs 1, 2). These temperature reconstructions are based largely on terrestrial records from extra-tropical or high-elevation sites; however, global average surface temperature changes closely follow those of the global tropics, which are 75% ocean. In particular, the tropical Indo-Pacific warm pool (IPWP) represents a major heat reservoir that both influences global atmospheric circulation and responds to remote northern high-latitude forcings. Here we present a decadally resolved continuous sea surface temperature (SST) reconstruction from the IPWP that spans the past two millennia and overlaps the instrumental record, enabling both a direct comparison of proxy data to the instrumental record and an evaluation of past changes in the context of twentieth century trends. Our record from the Makassar Strait, Indonesia, exhibits trends that are similar to a recent Northern Hemisphere temperature reconstruction. Reconstructed SST was, however, within error of modern values from about ad 1000 to ad 1250, towards the end of the Medieval Warm Period. SSTs during the Little Ice Age (approximately ad 1550-1850) were variable, and approximately 0.5 to 1 degrees C colder than modern values during the coldest intervals. A companion reconstruction of delta(18)O of sea water-a sea surface salinity and hydrology indicator-indicates a tight coupling with the East Asian monsoon system and remote control of IPWP hydrology on centennial-millennial timescales, rather than a dominant influence from local SST variation.