Anodontosaurus was named by Charles Mortram Sternberg in 1928, based on holotype CMN 8530, a partially preserved skeleton including the skull, half ring, armor and other postcranial remains. The badly crushed skeleton was collected by Sternberg in 1916 from a Canadian Museum of Nature quarry, 8 miles southwest of Morrin. It was collected from the upper part of the Lower Horseshoe Canyon Formation (unit 2), dating to the latest Campanian to the earliest Maastrichtian stage of the Late Cretaceous period, about 71-70.2 million years ago. The generic name means "toothless lizard" in Ancient Greek. It was inspired by the fact that compression damage to the specimen had removed the teeth, at the same time shifting various flat round elements below the skull and on top of the left lower jaw, misleading Sternberg into assuming that large "trituration plates" had replaced the normal dentition. The specific name, lambei, honours Lawrence Morris Lambe, the Canadian geologist and palaeontologist from the Geological Survey of Canada where the holotype was reposited.
Anodontosaurus was a medium-sized ankylosaurid that was quadrupedal, ground-dwelling and herbivorous. Like other ankylosaurs, Anodontosaurus has armor on a majority of the dorsal surfaces of its body. It has a wide, pointed tail club and the end of its armored tail. The skull features postocular caputegulae, which are small polygonal plates of bone that are present on the cranium and are situated to the immediate rear of the eye.