Meiolania (Fig. 1, Oligocene to Holocene-only 2000 years ago, Anderson 1925) was a giant horned turtle with a club tail, sort of like the Triassic turtle, Proganochelys (Fig. 2). According to Wikipedia, in Meiolania, “Two large horns faced sideways, giving the skull a total width of 60 centimetres (2.0 ft), and would have prevented the animal fully withdrawing its head into its shell.” The horns appear in a variety of shapes. More recent fossils are found in Australia and New Zealand but Cretaceous specimens are known from Argentina. So, like ankylosaurs, this turtle successfully faced down giant theropod dinosaurs.
Another Triassic turtle,
Proterochersis (Fig. 2), had a shell more like those found in typical turtles. Proterochersis is the earliest known Pleurodire (“side-necked”) turtle.
With this variety in turtles already found in Late Triassic strata, the origin of turtles must be much further back in time. Indeed…
The next prior step in the evolution of turtles
can be found in Stephanospondylus (Fig. 3) of the Early Permian. That gives Permian and Triassic turtles a good 70 million years to evolve and diversify to the grades we find in Proganochelys and Proterochersis. It’s worthwhile to compare these figures to note how far turtles have come and how their basic morphology arose in the Early Permian, fighting off our early ancestors among the ophiacodont and sphenacodont pelycosaurs alongside such as other heavy plant-eaters as Casea and the ancestors of Eunotosaurus.

Figure 3. Click to enlarge. Stephanospondylus parts roughly assembled. Note the origin of the carapace (upper shell) as a broad costal rib. The presence of a plastron (lower shell) is presumed by the distal articular surface of the pubis and the shape of the interclavicle.
Someday
Those tough little Permian and Triassic turtles will be found and they will make big news. Someday Stephanospondylus will be re-examined and appreciated for what it is and that will make big news.
Perhaps now a tip of the hat is due
to a more primitive turtle and Eunotosaurus ancestor, Milleretta (Fig. 4), which survived until the Late Permian, but must have had its origins in the Late Pennsylvanian, millions of years prior to the Early Permian and the appearance of Stephanospondylus. In the Late Pennsylvanian Milleretta was facing down smaller predators, like Palaeothyris and probably Protorothyris among the basal reptiles and Gephyrostegus among the most reptile-like amphibians.

Figure 4. Milleretta, a Late Permian descendant of the Late Pennsylvanian ancestor of turtles, Odontochelys and Eunotosaurus.
I haven’t forgotten Odontochelys
Odontochelys (Fig. 5, Late Triassic) is another descendant of an ancient sister to Milleretta (RC70) but diverged from the ancestors of today’s turtles as we discussed earlier.

Figure 5. Click to enlarge. Odontochelys the quasi-turtle in dorsal, lateral and ventral views. The same for the skull.
So the origin of turtles and the elaborations of their shell was essentially a race against ever larger and more vicious predators, following the Red Queen hypothesis. The ancestors of Meiolania survived until the point that a descendant of Proterothyris (Homo sapiens) finally wiped them out, a mere 2000 years ago. Happily, a variety of other turtles are still with us.
References
Anderson, C., 1925. Notes on the extinct Chelonian Meiolania, with a record of a new occurrence. Records of the Australian Museum 14(4): 223–242, plates xxx–xl. online pdf
Baur G 1887. On the phylogenetic arrangement of the Sauropsida: Journal of Morphology, v. 1, n. 1:93-104.
Broom R 1924. On the classification of the reptiles. Bulletin of the American Museum of Natural History 51:39-45.
Gaffney ES 1990. The comparative osteology of the Triassic turtle Proganochelys, Bull. Am. Mus. Nat. Hist. 194: 1–263.Geinitz HB and Deichmüller JV 1882. Die Saurier der unteren Dyas von Sachsen. Paleontographica, N. F. 9:1-46.
Gregory WK 1946. Pareiasaurs versus placodonts as near ancestors to turtles. Bulletin of the American Museum of Natural History 86:275-326.
Joyce WG, Schoch RR and Lyson TR 2013. The girdles of the oldest fossil turtle, Proterochersis robusta, and the age of the turtle crown. BMC Evolutionary Biology 13: 266. doi:10.1186/1471-2148-13-266 abstract
Kissel R 2010. Morphology, Phylogeny, and Evolution of Diadectidae (Cotylosauria: Diadectomorpha). Toronto: University of Toronto Press. pp. 185. online pdf
Li C, Wu X-C, Rieppel O, Wang L-T, Zhao L-J 2008. An ancestral turtle from the Late Triassic of southwestern China. Nature 456: 497-501.
Lyson TR, Sperling EA, Heimberg AM, GauthierJA, King BL, and Peterson KJ 2011.MicroRNAs support a turtle + lizard clade. Biol Lett 2011 : rsbl.2011.0477v1-rsbl20110477.abstract – online news story
Reisz RR and Head JJ 2008. Turtle origins out to sea. Nature 456, 450–451.
Rieppel O and deBraga M 1996. Turtles as diapsid reptiles. Nature 384:453-454.
Rieppel O and Reisz RR 1999. The Origin and Early Evolution of Turtles. Annual Review of Ecology and Systematics 30: 1-22.
Romer AS 1925. Permian amphibian and reptilian remains described as Stephanospondylus. Journal of Geololgy 33: 447-463.
Stappenbeck R 1905. Uber Stephanospondylus n. g. und Phanerosaurus H. v. Meyer: Zeitschrift der Deutschen Geologischen Gesellschaft, v. 57, p. 380-437.
Williston SW 1917. The phylogeny and classification of Reptilies. Journal of Geology 28: 41-421.