Apatite fission-track (AFT) analysis of core samples from seven deep oil wells in Oklahoma, Texas, and northeastern New Mexico indicates that the base of a middle Cenozoic apatite partial annealing zone (PAZ) is preserved in the subsurface. The base of the PAZ, which approximately corresponds to the 110°C paleoisotherm, is at a subsurface depth of ~3000 m in the Anadarko Basin, at ~825 m at the NM-TX stateline and emerges from the subsurface, projecting into the air, near the Pecos River in eastern New Mexico. The AFT cooling age just beneath the base of the PAZ is ~27 Ma in northeastern New Mexico and ~38 Ma in the Anadarko basin. Triassic sandstones exposed at the surface between Santa Rosa, NM, in the Pecos River valley and Albuquerque, NM, on the western margin of the Rio Grande rift yield AFT ages of 25 to 30 Ma. Thermal modeling combined with AFT data from the Hagan embayment northeast of Albuquerque indicates that a heat flow >84 mW/m² and at least 2 km of denudation are needed to explain the distribution of AFT ages. In addition, modeling of AFT age and length data from the south end of the Wet Mountains, Colorado, suggests that paleotemperatures were ~95°C at the base of the range at ~25 Ma. This data, when linked with the preservation of the Rocky Mountain erosion surface beneath 33 Ma andesite flows on Greenhorn Mountain, can be used to calculate a middle Cenozoic paleogeothermal gradient of ~47°C/km for this area.