Le Mastodonsaurus ressemblait à une énorme grenouille. Sa tête, au lieu d'être en demi-cercle comme chez les grenouilles, était triangulaire et atteignait 1,25 mètres de long. La longueur totale de l'animal était donc d'environ 4 à 6 mètres. Les mâchoires étaient armées de dents coniques. Le corps était relativement faible par apport à leur grosse tête, et la queue était très courte.

Selon certains scientifiques, Mastodonsaurus était incapable de sortir de l'eau. Cette option est confirmée par les trouvailles de grandes quantités d'ossements qui montrent que dans les périodes de sécheresse ces animaux sont morts en masse.

Un grand nombre d'espèces a été attribués au genre au fil des ans. Toutefois, dans un réexamen de ce genre par Markus Moser et Rainer Schoch en 2007, seule trois espèces ont été déterminées pour être valides.

• Mastodonsaurus jaegeri (Europe)
• Mastodonsaurus giganteus (Europe)
• Mastodonsaurus torvus (Russie)

Georg Friedrich Jaeger a décrit le premier Mastodonsaurus en 1828. Il l'avait nommé d'après une seule dent qu'il avait estimé être celle d'un reptile. 

La dénomination des premiers spécimens a cependant été contestée. Léopold Fitzinger a renommé l'animal Batrachosaurus en 1837. En 1841, le paléontologue anglais Richard Owen a proposé le nom Labyrinthodon pour décrire ses dents très pliées ou labyrinthiques. Owen pensait que le nom Mastodonsaurus ne devait pas être conservé, car il rappelle inévitablement l'idée du mastodonte (un genre de mammifère) ou bien une forme de dent en mammelon. Egalement, le deuxième élément du nom, saurus, indique une fausse parenté, l'animal n'étant pas un saurien, mais un batracien.

Owen avait reconnu que l'animal n'était pas un reptile. De ce fait, il le rapprocha au genre Phytosaurus de Jaeger. Bien que les deux animaux aient été de taille similaire avec des dents coniques, Phytosaurus se révéla plus tard être un reptile ressemblant à un crocodile. 

Des éléments supplémentaires, notamment le crâne, ont solidement placé le genre Labyrinthodon comme un amphibien. Jaeger avait également créé l'espèce Salamandroides giganteus en 1828, en se basant sur une portion d'occiput. En 1833, il a décrit un crâne complet de Salamandroides giganteus qui avait les mêmes dents que son Mastodonsaurus, ce qui en fait le premier crâne complet d'un temnospondyle. Comme Mastodonsaurus avait été attribué en premier, il a eu priorité sur les autres noms qui sont devenus des synonymes.