Sea turtles (Chelonioidea) are a prominent group of modern marine reptiles whose early history is poorly understood. Analysis of exceptionally well preserved fossils of Bouliachelys suteri gen. et sp. nov., a large-bodied basal protostegid (primitive chelonioid) from the Early Cretaceous (Albian) of Australia, indicates that early sea turtles were both larger and more diverse than previously thought. The analysis implies at least five distinct sea turtle lineages existed around 100 million years ago. Currently, the postcranially primitive Ctenochelys and Toxochelys are interpreted as crown-group sea turtles closely related to living cheloniids (e.g. Chelonia); in contrast, the new phylogeny suggests that they are transitional (intermediate stem-taxa) between continental testudines and derived, pelagic chelonioids.