The oldest discoveries of fossil turtles now included under Solitudo were made in the 19th century, with Leith-Adams describing remains from Zebbug Cave (Malta) as Testudo robusta.

These remains were described in 2022 by Valenti and colleagues, who found sufficient anatomical evidence to establish a new genus they dubbed Solitudo, with "Testudo" robusta serving as the type species.

[3] The name Solitudo derives from the Latin word for loneliness or solitude, which reflects the isolation of islands where members of this genus have been found.

[4] Although repeated attempts at extracting genetic material were conducted, no methods yielded DNA which rendered molecular phylogenetic analysis impossible.

Due to this restriction, the relationship between Solitudo and other circum-Mediterranean tortoises was established on the basis of femur morphology, which is well known in the relevant taxa.

Besides the three named species of Solitudo, a fourth, unnamed taxon from Monte Pellegrino was also found to fall within the "Insular morphotype", sharing the unfused trochanter that defines the clade.

The exact relationship between Solitudo and the other tortoises surrounding the Mediterranean remains unknown until better material, in particular fossils of the head and shell, is found.

Solitudo sicula would have shared its home island with the extant Hermann's Tortoise, which has been continuously present on Sicily since at least the Middle Pleistocene.