The Greenland ice sheet (GrIS) contains the largest store of fresh water in the Northern Hemisphere, equivalent to ∼7.4 m of eustatic sea-level rise, but its impacts on current, past, and future sea level, ocean circulation, and European climate are poorly understood. Previous estimates of GrIS melt, from 26 yr of satellite observations and temperature-driven melt models over 48 yr, show increasing melt trends. There are, however, no runoff data of comparable duration with which to validate the relationship between the spatial extent of melting and runoff or temperature-based runoff models. Further, longer runoff records are needed to extend the melt pattern of Greenland to centennial timescales, enabling recent observations and trends to be put into a better historical context. We have developed a new GrIS runoff proxy by extracting information on relative salinity changes from annual growth bands of red coralline algae. We observed significant negative relationships between historic runoff, relative salinity, and marine summer temperature in Søndre Strømfjord, Greenland. We produce the first reconstruction of runoff from a section of the GrIS that discharges into Søndre Strømfjord over several decades (1939–2002) and record a trend of increasing reconstructed runoff since the mid 1980s. In situ summer marine temperatures followed an equivalent trend. We suggest that since A.D. 1939, atmospheric temperatures have been important in forcing runoff. These results show that our technique has significant potential to enhance understanding of runoff from large ice sheets as it will enable melt reconstruction over centennial to millennial timescales.