Cervical vertebrae of azhdarchid pterosaurs were discovered in two Upper Cretaceous (Baynshire Suite) dinosaur localities, Bayshin Tsav and Burkhant, in the Gobi Desert. These are the first discoveries of pterosaur remains in the Upper Cretaceous of Mongolia. The Burkhant specimen includes a nearly complete atlas-axis complex, which has rarely been described in this clade of pterosaurs. Although all elements comprising this complex are fused together, a wing-like atlas neural arch is still discernable. The postzygapophyseal facet of the axis is long anteroposteriorly and convex dorsally, and would likely have allowed a fairly large range of dorsoventral flexion at the axis-third cervical joint unlike in other well-known ornithocheiroids such as Pteranodon and Anhanguera. Both Mongolian localities represent inland, terrestrial environments, which were apparently not typical habitats of pterosaurs, thus adding further evidence for the ubiquity of Azhdarchidae during the Late Cretaceous.