Belemnites (order Belemnitida), a very successful group of Mesozoic cephalopods, provide an important clue for understanding Mesozoic marine ecosystems and the origin of modern cephalopods. Following current hypotheses, belemnites originated in the earliest Jurassic (Hettangian, 201.6–197 Ma) with very small forms. According to this view their paleobiogeographic distribution was restricted to northern Europe until the Pliensbachian (190–183 Ma). The fossil record is, however, biased by the fact that all the previous studies on belemnites focused on Europe. Here we report two belemnite taxa from the Hettangian of Japan: a new species of the Sinobelemnitidae and a large taxon of the suborder Belemnitina. The Sinobelemnitidae, which may be included in the future in a new suborder, have also been recorded from the Triassic of China, specimens so far poorly understood. The presence of a very large rostrum attributed to the Belemnitina suggests in addition that a diverse belemnite fauna evolved earlier than previously thought. Our new findings therefore (1) extend the origin of the belemnites back by ∼33 m.y. into the Triassic, (2) suggest that this group did not necessarily originate in northern Europe, and (3) imply that belemnites survived the Triassic–Jurassic extinction, one of the five big mass extinctions in the Phanerozoic. Since belemnites provided a considerable amount of food as prey, the origination of belemnites is probably an important event also for the evolution of their predators, such as marine reptiles and sharks.