Recovery of three new partial skulls of Palatobaena bairdi from the latest Cretaceous (Lancian) and middle Paleocene (Torrejonian) of Montana and from the early Paleocene of Colorado adds greatly to the knowledge of this peculiar baenid turtle. Although there is some variation in the temporal emargination, Palatobaena primitively appears to have had a deep emargination as seen in eubaenines. The wide triturating surfaces align Palatobaena with the Eubaeninae. A skull of a new species found in the Wasatch Formation (Wasatchian), Wyoming, belongs to this genus and extends the record of Palatobaena into the early Eocene. The new species has a relatively shorter skull and its jaw mechanics represents a further specialization from the morphology seen in P.bairdi.