Although our knowledge of the fossil record of early theropod dinosaurs has greatly improved over the last two decades, very little is known about European taxa because they are largely incomplete. Here we present an exceptionally well-preserved theropod skeleton from the Late Triassic of Europe, pertaining to a new genus and species. The specimen includes a nearly complete skull, two articulated forelimbs and stomach contents. Notatesseraeraptor frickensis gen. et sp. nov. is an early-diverging neotheropod with affinities to Dilophosaurus and Averostra and displays an interesting mixture of character states typically seen either in coelophysids or in dilophosaurids. Based on our phylogenetic analysis, N. frickensis gen. et sp. nov. is considered one of the currently oldest and most basal members of the lineage, leading to Averostra. A monophyletic ‘traditional Coelophysoidea’ including Dilophosaurus is not supported.