Insects are the most diverse lineage of all life in numbers of species, and ecologically they dominate terrestrial ecosystems. However, how and when this immense radiation of animals originated is unclear. Only a few fossils provide insight into the earliest stages of insect evolution, and among them are specimens in chert from Rhynie, Scotland's Old Red Sandstone (Pragian; about 396-407 million years ago), which is only slightly younger than formations harbouring the earliest terrestrial faunas. The most well-known animal from Rhynie is the springtail Rhyniella praecursor (Entognatha; Collembola), long considered to be the oldest hexapod. For true insects (Ectognatha), the oldest records are two apparent wingless insects from later in the Devonian period of North America. Here we show, however, that a fragmentary fossil from Rhynie, Rhyniognatha hirsti, is not only the earliest true insect but may be relatively derived within basal Ectognatha. In fact, Rhyniognatha has derived characters shared with winged insects, suggesting that the origin of wings may have been earlier than previously believed. Regardless, Rhyniognatha indicates that insects originated in the Silurian period and were members of some of the earliest terrestrial faunas.