A dentary bone containing several teeth, from the Middle Jurassic (Bathonian) of northwestern Madagascar is described as the type of a new sauropod dinosaur taxon, Archaeodontosaurus descouensi, n.g., n.sp. This taxon is characterised by the unusual combination of a dentary with a deep anterior part, as in advanced sauropods, and teeth with large serrations and a convex lingual side, which resemble the teeth of prosauropods. A more common pattern in early sauropods is the combination of a low, prosauropod-like dentary and spoon-shaped, sauropod-like teeth. Although the condition in Archaeodontosaurus descouensi strongly suggests that basal sauropods had prosauropod-like teeth, what is known of the jaw and dentition in various early and middle Jurassic sauropods indicates mosaic evolution along different paths during the early diversification of the group. Archaeodontosaurus descouensi differs from Jurassic sauropod material from Madagascar, previously described as Bothriospondylus and Lapparentosaurus, which needs revision. It appears that at least two distinct sauropods, with different tooth morphologies, are present in the Middle Jurassic of Madagascar.