The holotype of Tseajaia is a nearly complete skeleton, specimen UCMP V4225 / 59012, which is from the lowermost Organ Rock Shale or uppermost Cedar Mesa Sandstone.

It was discovered by a field party led by Charles L. Camp working in San Juan County, Utah in June, 1942.

The genus name comes from "Tse Ajai" ("Rock Heart"), a nearby igneous plug used as a landmark by the Navajo.

[8] Additional finds allowing for a better taxonomic analysis indicate they belong in the Diadectomorpha, as the sister group to the large and more derived Diadectidae.

Tseajaia itself being a fairly generalized form, gives a reasonable indication of the build and looks of the closest relatives of the amniotes.