The origin of land plants is one of the most important evolutionary events in Earth’s history. The mode and timing of the terrestrialization of plants remains debated and previous data indicate Gondwana to be the center of land-plant radiation at ~ 470–460 Ma. Here we present the oldest occurrences of trilete spores, probably the earliest traces of vascular land plants yet recorded. The spores occur in Ordovician, Sandbian (455 million years old) successions in central Sweden, once part of the paleocontinent Baltica. These strata are independently dated by marine microfossils (conodonts) and 206Pb/238U dating of volcanic ash deposits. Our discovery extends the record of trilete spores globally by ~8 million years, and for Baltica by ~25 million years. Additionally, cryptospore assemblages are identified revealing a diverse and stable mid-Ordovician (Darriwilian: ~ 460 Ma) vegetation of free-sporing plants. The formation of regolith substrates on land as a consequence of permanent plant cover must in turn have affected the marine biota. We link these early land plant spore occurrences to the extensive, nutrient-rich volcanic ash deposits and propose Baltica as the possible original region of the radiation of early land plants.