Fishflies (Corydalidae: Chauliodinae) are one of the main groups of the basal holometabolous insect order Megaloptera, with ca. 130 species distributed worldwide. A number of genera from the Southern Hemisphere show remarkably disjunctive distributions and are considered to be the austral remnants or “living fossils” of Gondwana. Hitherto, the evolutionary history of fishflies remains largely unexplored due to limited fossil record and incomplete knowledge of phylogenetic relationships. Here we describe two significant fossil species of fishflies, namely Eochauliodes striolatus gen. et sp. nov. and Jurochauliodes ponomarenkoi Wang & Zhang, 2010 (original designation for fossil larvae only), from the Middle Jurassic of Inner Mongolia, China. These fossils represent the earliest fishfly adults. Furthermore, we reconstruct the first phylogenetic hypothesis including all fossil and extant genera worldwide. Three main clades within Chauliodinae are recognized, i.e. the Dysmicohermes clade, the Protochauliodes clade, and the Archichauliodes clade. The phylogenetic and dispersal-vicariance (DIVA) analyses suggest Pangaean origin and global distribution of fishflies before the Middle Jurassic. The generic diversification of fishflies might have happened before the initial split of Pangaea, while some Gondwanan-originated clades were likely to be affected by the sequential breakup of Pangaea. The modern fauna of Asian fishflies were probably derived from their Gondwanan ancestor but not the direct descendents of the Mesozoic genera in Asia.