Barameda decipiens, gen. nov. (Woodward, 1906) is described from the Early Carboniferous Mansfield Group, Victoria, Australia. It differs from other rhizodontiforms ( Strepsodus, Rhizodus, Screbinodus, Sauripterus) by the shape of the skull roofing bones, course of the supratemporal sensory line, vertebral structure, and pectoral fin skeleton. The skull roof of Barameda, gen. nov., differs from that of Osteolepiformes in having a larger extratemporal bone that contacts the intertemporal, by the overlap areas on the intertemporal, and in having fewer snout bones. The cheek has a very large postorbital bone, and the lacrimai is narrow. There are two external nostrils, which are situated close together and differ in their position in the only other rhizodontiform for which they are known, suggesting that the group was not choanate. Rhizodontiforms are a monophyletic group characterized by specializations of the pectoral girdle and fin. They may be placed in Schultze’s (1987) scheme of osteichthyan interrelationships as the sister group to Osteolepiformes plus Tetrapoda, with which they share polyplocodont tooth structure, a similar cheek pattern, and a large humerus with well developed muscle attachment processes and prominent entepicondyle, and articulating with two large bones, the ulna and radius. Barameda, gen. nov., is regarded as the plesiomorphic sister taxon to the British rhizodontiforms ( Strepsodus, Rhizodus, Screbinodus), as it lacks the main lateral-line canal looping into the parietal and has a broad dorsal division on the cleithrum.