Fossils of Mesozoic terrestrial vertebrates from Lithuania and the wider East Baltic region of Europe have previously been unknown. We here report the first Mesozoic terrestrial vertebrate fossils from Lithuania: two premaxillary specimens and three teeth that belong to Phytosauria, a common clade of semiaquatic Triassic archosauriforms. These specimens represent an uncrested phytosaur, similar to several species within the genera Paleorhinus, Parasuchus, Rutiodon and Nicrosaurus. Because phytosaurs are currently only known from the Upper Triassic, their discovery in northwestern Lithuania (the Šaltiškiai clay-pit) suggests that at least part of the Triassic succession in this region is Late Triassic in age, and is not solely Early Triassic as has been previously considered. The new specimens are among the most northerly occurrences of phytosaurs in the Late Triassic, as Lithuania was approximately 7–10° further north than classic phytosaur-bearing localities in nearby Germany and Poland, and as much as 40° further north than the best-sampled phytosaur localities in North America. The far northerly occurrence of the Lithuanian fossils prompts a review of phytosaur biogeography and distribution, which suggests that these predators were widely distributed in the Triassic monsoonal belt but rarer in more arid regions.