Over the last decade, two major calving events of the Petermann Ice Tongue in Northwest Greenland have led to speculation on its future stability and contribution to further Greenland Ice Sheet mass loss. However, it has been unclear if these events are anomalous or typical within the context of limited historical observations. We extend the historical record of the floating ice tongue using the stratigraphy of Petermann Fjord sediments to provide a longer-term perspective. Computed tomography (CT) scans, X-Ray Fluorescence (XRF) scans, Ice-Rafted Debris (IRD) counts, and the magnetic properties of specific particle size fractions constrain changes in depositional processes and sediment sources at our core sites, allowing for reconstructions of past behavior of the Petermann Ice Tongue. Radiocarbon dating of foraminifera, Pb-210, and paleomagnetic secular variation (PSV) provide age control and help to address uncertainties in radiocarbon reservoir ages. A floating ice tongue in Petermann Fjord formed in late glacial time as Petermann Glacier retreated from an advanced grounded position. This paleo-ice tongue broke-up during the early Holocene when high northern latitude summer insolation was higher than present. After gradual regrowth of the ice tongue associated with regional cooling, the ice tongue reached its historical extent only within the last millennium. Little or no ice tongue was present for nearly 5000 years during the middle Holocene, when decadal mean regional temperatures are estimated to be 0.8-2.9 degrees C higher than preindustrial (1750 CE) and seasonal sea-ice in the Lincoln Sea was reduced. This pre-historical behavior shows that recent anthropogenic warming may already be in the range of ice tongue instability and future projected warming increases the risk of ice tongue break-up by the mid-21st Century.