Following the end-Permian extinction, terrestrial vertebrate diversity recovered by the Middle Triassic, and that diversity was now dominated by reptiles. However, those reptilian clades, including archosaurs and their closest relatives, are not commonly found until ~30 million years post-extinction in Late Triassic deposits despite time-calibrated phylogenetic analyses predicting an Early Triassic divergence for those clades. One of these groups from the Late Triassic, Phytosauria, is well known from a near-Pangean distribution, and this easily recognized clade bears an elongated rostrum with posteriorly retracted nares and numerous postcranial synapomorphies that are unique compared with all other contemporary reptiles. Here, we recognize the exquisitely preserved, nearly complete skeleton of Diandongosuchus fuyuanensis from the Middle Triassic of China as the oldest and basalmost phytosaur. The Middle Triassic age and lack of the characteristically-elongated rostrum fill a critical morphological and temporal gap in phytosaur evolution, indicating that the characteristic elongated rostrum of phytosaurs appeared subsequent to cranial and postcranial modifications associated with enhanced prey capture, predating that general trend of morphological evolution observed within Crocodyliformes. Additionally, Diandongosuchus supports that the clade was present across Pangea, suggesting early ecosystem exploration for Archosauriformes through nearshore environments and leading to ease of dispersal across the Tethys.