Oxygen and hydrogen isotope ratios in polar precipitation are widely used as proxies for local temperature. In combination, oxygen and hydrogen isotope ratios also provide information on sea surface temperature at the oceanic moisture source locations where polar precipitation originates. Temperature reconstructions obtained from ice-core records generally rely on linear approximations of the relationships among local temperature, source temperature, and water-isotope values. However, there are important nonlinearities that significantly affect such reconstructions, particularly for source region temperatures. Here, we describe a relatively simple water-isotope distillation model and a novel temperature reconstruction method that accounts for these nonlinearities. Further, we examine in detail many of the parameters, assumptions, and uncertainties that underlie water-isotope distillation models and their influence on these temperature reconstructions. We provide new reconstructions of absolute surface temperature, condensation temperature, and source region evaporation temperature for all long Antarctic ice-core records for which the necessary data are available. These reconstructions differ from previous estimates due to both our new model and reconstruction technique, the influence of which is investigated directly. We also provide thorough uncertainty estimates for all temperature histories. Our reconstructions constrain the pattern and magnitude of polar amplification in the past and reveal asymmetries in the temperature histories of East and West Antarctica.