Each piece of data is valuable for unearthing the earliest history of tetrapod origin. Despite frequently incomplete preservation, each skeletal element provides important information on the morphology, phylogeny and faunistic diversity of early tetrapodomorphs. We describe here new and earlier collected material from the fossil vertebrate site Yam-Tesovo on the Oredezh River (Leningrad Region, northwestern Russia) in the deposits of the Yam-Tesovo Formation within the Amata Regional Stage (?lowermost Frasnian, Upper Devonian). Upon similarity of their dermal ornamentation, two mandibular fragments are suggested to belong to the new tetrapodomorph taxon Rubrognathuskuleshovi n. gen. et sp. This species demonstrates a general ‘elpistostegalian' morphological pattern with some early tetrapod characters. The new taxon is characterised by an almost closed intercoronoid fossa, a prearticular that is strongly convex in section and bearing small teeth along its dorsal margin, low vertical coronoid laminae and coronoid fangs that enter the coronoid tooth row. The mandibular canal runs partly in open groove or opens to the surface by a row of large pores. The dermal ornament consists of a network of small ridges forming tubercles in the nodes. The postfrontal assigned to Tetrapodomorpha shows a ‘tetrapod-like' pits-and-ridges sculpturing and a supraorbital ridge characteristic of early tetrapods as well as ‘elpistostegalians'. Its long posterolateral bone margin demonstrates a lateral projection similar to that in Tiktaalik and unknown in other ‘elpistostegalians' and early tetrapods. An unusually flattened vomer is doubtfully related to the tetrapodomorph genus Livoniana Ahlberg, Lukševičs & Mark-Kurik, 2000, based upon characteristic multiple tooth rows. Teeth in rows decrease labially and show no clearly enlarged fang pairs. New finds of the last two decades present the earliest records of some tetrapod characters in non-limbed tetrapodomorphs. This challenges previous hypotheses on the origin of tetrapods.