Similar to the still-extant, possibly closely related Dermochelyidae, protostegids possessed extremely reduced carapaces.

[9] The family's oldest members include an Early Cretaceous (Valanginian) taxon described on the basis of limb bones and shell remains from the Rosablanca Formation of Colombia,[2] Desmatochelys padillai, known from the specimens recovered from the Early Cretaceous Paja Formation of Colombia[10] and Santanachelys gaffneyi, known from a specimen excavated from Brazil in 1998.

[4][12] Conversely, the phylogenetic analyses conducted by Joyce (2007) and Anquetin (2012), which included one protostegid species (Santanachelys gaffneyi), recovered the family as only distantly related to leatherback turtles.

Joyce (2007) recovered Protostegidae as basal eucryptodiran turtles lying outside the crown group of Cryptodira (the least inclusive clade containing all living cryptodirans) and closely related to Solnhofia parsonsi;[13] Santanachelys had a similar phylogenetic position in the analysis conducted by Anquetin (2012), who stressed that future studies should include more protostegids to confirm this phylogenetic placement.

[13] The analyses conducted by Sterli (2010) and Sterli & de la Fuente (2011) recovered Santanachelys (and, presumably, the entirety of Protostegidae) as even more distantly related to living cryptodirans; it was found to be basal turtle lying outside the crown group of turtles (the least inclusive clade containing cryptodirans and pleurodirans).

[10] In 1888, the Belgian zoologist George Albert Boulenger published his classification of the Testudinata within the 9th edition of the Encyclopædia Britannica.

[17] In 1994, Hirayama proposed a three-family subdivision of the sea turtle superfamily based on cladistic analysis; Protostegidae was given full, formal family status in the system, containing most of the extinct genera, including Archelon, and a previously undescribed protostegid.