Pochodzenie Żółwie pojawiły się prawdopodobnie na przełomie paleozoiku i mezozoiku, ok. 255 mln lat temu, na co wskazuje datowanie molekularne. Już wcześniej, w środkowym permie żyli ich domniemani przodkowie, roślinożerne parejazaury (Pareiasauria). Paleontolodzy nie odnaleźli jednak form pośrednich, które łączyłyby je z prymitywnymi gadami z karbonu. Ze względu na czaszkę bez otworów skroniowych żółwie tradycyjnie traktowano jako przedstawicieli Anapsida – co wspierają też niektóre nowsze analizy – lub, rzadziej, za lepidozauromorfy. Praktycznie wszystkie analizy molekularne wskazują, że żółwie to diapsydy, które utraciły otwory skroniowe. Na podstawie analizy sekwencji mikroRNA zasugerowano bliskie pokrewieństwo żółwi z lepidozaurami, jednak wyniki tych badań zostały skrytykowane, a niemal wszystkie pozostałe badania molekularne łączą żółwie z archozaurami. Dopiero stosunkowo niedawno dostrzeżono pewne cechy morfologiczne, takie jak budowa kości bocznoklinowej u wczesnych żółwi i Archosauriformes, które wspierają hipotezę o bliskim pokrewieństwie żółwi i archozaurów. Również niektóre inne cechy mogą stanowić synapomorfie łączące te dwa klady.