Polar ice core records attest to a colossal volcanic eruption that took place ca. A.D. 1257 or 1258, most probably in the tropics. Estimates based on sulfate deposition in these records suggest that it yielded the largest volcanic sulfur release to the stratosphere of the past 7,000 y. Tree rings, medieval chronicles, and computational models corroborate the expected worldwide atmospheric and climatic effects of this eruption. However, until now there has been no convincing candidate for the mid-13th century “mystery eruption.” Drawing upon compelling evidence from stratigraphic and geomorphic data, physical volcanology, radiocarbon dating, tephra geochemistry, and chronicles, we argue the source of this long-sought eruption is the Samalas volcano, adjacent to Mount Rinjani on Lombok Island, Indonesia. At least 40 km3 (dense-rock equivalent) of tephra were deposited and the eruption column reached an altitude of up to 43 km. Three principal pumice fallout deposits mantle the region and thick pyroclastic flow deposits are found at the coast, 25 km from source. With an estimated magnitude of 7, this event ranks among the largest Holocene explosive eruptions. Radiocarbon dates on charcoal are consistent with a mid-13th century eruption. In addition, glass geochemistry of the associated pumice deposits matches that of shards found in both Arctic and Antarctic ice cores, providing compelling evidence to link the prominent A.D. 1258/1259 ice core sulfate spike to Samalas. We further constrain the timing of the mystery eruption based on tephra dispersal and historical records, suggesting it occurred between May and October A.D. 1257.