Spiny-bracted fruits of Palaeocarpinus Crane, a genus of Betulaceae previously known only from Europe and North America, have been discovered in the Paleocene of Altai, northwestern China. The fruits are found in association with abundant Corylus-like foliage and staminate catkins containing Corylus-like pollen. Because of problems distinguishing leaves of Corylus from those of extinct betulaceous genera, we place these leaves in the genus Corylites Gardner ex Seward & Holttum. The fruits, staminate catkins, pollen, and leaves from Altai were probably all produced by a single species. Palaeocarpinus orientalis is nearly identical in its morphology to Palaeocarpinus joffrensis from the Paleocene of North America except in the more rounded primary bracts of the associated staminate catkins. The species is less similar to Palaeocarpinus laciniata from the Paleocene of southern England.