Autonomous Lagrangian Circulation Explorer floats recorded temperatures in depths between 700 and 1100 meters in the Southern Ocean throughout the 1990s. These temperature records are systematically warmer than earlier hydrographic temperature measurements from the region, suggesting that mid-depth Southern Ocean temperatures have risen 0.17 degrees C between the 1950s and the 1980s. This warming is faster than that of the global ocean and is concentrated within the Antarctic Circumpolar Current, where temperature rates of change are comparable to Southern Ocean atmospheric temperature increases.