The fossil history of most extant seed plant groups is relatively well documented. Cycads, conifers and Ginkgo all have an extensive fossil record, and the understanding of early angiosperm diversity is increasing. The Gnetales are an exception. Few macrofossils have been described, and character evolution within the group is poorly known. Cratonia cotyledon is a new gnetalean fossil from the Early Cretaceous Crato Formation of Brazil. This well-preserved seedling consists of two cotyledons, a feeder and a root. The leaf surface shows polygonal epidermal cells and apparently paracytic or actinocytic stomata. The cotyledons have a very specific venation pattern, shared only by Cratonia and Welwitschia, with parallel primary veins and secondary veins fusing to form inverted 'Y's between the main veins. Based on the 'Y'-venation and the presence of a feeder, we assign Cratonia to the Gnetum-Welwitschia clade. Fossil seedlings are unusual and this complete specimen with unambiguously welwitschioid characters is spectacular. Cratonia indicates that the evolutionary split between Gnetum and Welwitschia had occurred in the Early Cretaceous. Further, the close relationship between a West African plant and an east South American Early Cretaceous fossil is consistent with a major geological event: the rifting of the Gondwana continent.