Ornithomimosauria consists of the ostrich-mimic dinosaurs, most of which showing cursorial adaptations, that often exhibit features indicative of herbivory. Recent discoveries have greatly improved our knowledge of their evolutionary history, including the divergence into Ornithomimidae and Deinocheiridae in the Early Cretaceous, but the early part of their history remains obscured because their fossil remains are scarce in the Aptian–Albian sediments. In recent years, many isolated ornithomimosaur remains have been recovered from the Aptian Kitadani Formation of Fukui, central Japan. These remains represent multiple individuals that share some morphological features common to them but unknown in other ornithomimosaurs, suggesting a monospecific accumulation of a new taxon. As a result of the description and phylogenetic analysis, the Kitadani ornithomimosaur is recovered as a new genus and species Tyrannomimus fukuiensis, the earliest definitive deinocheirid that complements our knowledge to understand the early evolutionary history of Ornithomimosauria. Due to its osteological similarity to Tyrannomimus, a taxon previously considered an early tyrannosauroid based on fragmentary specimens, namely Aviatyrannis jurassica, may represent the earliest ornithomimosaur from the Upper Jurassic of Europe, significantly expanding the temporal and biogeographic range of Ornithomimosauria. This finding fills a 20-million-year ghost lineage of Ornithomimosauria implied by the presence of the oldest fossil record of Maniraptora from the Middle Jurassic and is consistent with the hypothesis that their biogeographic range was widespread before the Pangaean breakup in the Kimmeridgian.