Climate change is rapidly modifying tundra vegetation productivity and composition in the Arctic. However, empirical long-term evidence of this process is lacking due to field measurement limitations and problematic interpretation of the greening vs. browning from satellite data. Here, we measured plant-derived biomarkers from an Arctic fjord sediment core as proxies to reconstruct past changes in the tundra vegetation during the transition from the Little Ice Age to Modern Warming. Our findings reveal a rapid expansion of the tundra since the beginning of the twentieth century, largely coinciding with the decline of summer sea ice extent and glacier retreat. The greening trend inferred by biomarker analysis peaked significantly in the late 1990s, along with a shift in the tundra community toward a more mature successional stage. Most of this signal was consistent with the biomolecular fingerprint of vascular plant species more adapted to warmer conditions and widely expanding in proglacial areas during recent decades. Our results suggest that vegetation cover in Arctic fjords will drastically increase under the predicted warming scenario and sea ice loss, leading also to a significant change in tundra community structure.