The Visean stage of the Mississippian was a time of rapid tetrapod diversification which marks the earliest appearance of temnospondyls, microsaurs and the limbless aïstopods. Tetrapod finds from this stage are very rare and only a dozen sites are known worldwide. Here we announce the discovery of a new Visean site in Fife, Scotland, of Asbian age, and from it describe a new species of the baphetoid Spathicephalus. These specimens represent the oldest known baphetoid by three million years, yet belong to the most specialized members of the clade. Unlike typical baphetoids with large marginal teeth and palatal fangs characteristic of early tetrapods, spathicephalids had very broad flattened heads with a dentition consisting of a large number of small, uniform teeth. Spathicephalids were probably one of the earliest tetrapod groups to use suction feeding on small, aquatic prey. Palynological and sedimentological analysis indicates that the new fossil bed was deposited in a large, stratified, freshwater lake that became increasingly saline.