We show that southern elephant seal (Mirounga leonina) colonies existed proximate to the Ross Ice Shelf during the Holocene, well south of their core sub-Antarctic breeding and molting grounds. We propose that this was due to warming (including a previously unrecognized period from approximately 1,100 to 2,300 (14)C yr B.P.) that decreased coastal sea ice and allowed penetration of warmer-than-present climate conditions into the Ross Embayment. If, as proposed in the literature, the ice shelf survived this period, it would have been exposed to environments substantially warmer than present.