Pterosaurs are the oldest known powered flying vertebrates. Originating in the Late Triassic, they thrived to the end of the Cretaceous. Triassic pterosaurs are extraordinarily rare and all but one specimen come from marine deposits in the Alps. A new comparatively large (wing span >150 cm) pterosaur, Caelestiventus hanseni gen. et sp. nov., from Upper Triassic desert deposits of western North America preserves delicate structural and pneumatic details not previously known in early pterosaurs, and allows a reinterpretation of crushed Triassic specimens. It shows that the earliest pterosaurs were geographically widely distributed and ecologically diverse, even living in harsh desert environments. It is the only record of desert-dwelling non-pterodactyloid pterosaurs and predates all known desert pterosaurs by more than 65 Myr. A phylogenetic analysis shows it is closely allied with Dimorphodon macronyx from the Early Jurassic of Britain.