The holotype specimen of Navajodactylus was discovered and collected by oceanographer Arjan C. Boeré from the Kirtland Formation in 2002. Navajodactylus was first named by Robert M. Sullivan and Denver W. Fowler in 2011 and the type species is Navajodactylus boerei. The generic name honors the Navajo Nation, combining their name with a Greek δάκτυλος, daktylos, "finger". The specific name honors Arjan C. Boeré.^[1]

Navajodactylus is based on the holotype SMP VP-1445, from the Hunter Wash Member of the Kirtland Formation, San Juan Basin, dating to the upper Campanian, about 75 million years old. It consists of three pieces of the first phalanx of the wing finger. The paratype is SMP VP-1853, an ulna fragment. Two first phalanges, TMP 72.1.1 and TMP 82.19.295, both from the Dinosaur Park Formation of the Dinosaur Provincial Park, Alberta, were referred to this taxon,^[1] but in 2019, Hone et al. recognized these as referable to their new azhdarchid Cryodrakon.^[2]

Navajodactylus was a medium-sized pterosaur, with an estimated wingspan of 3.5 meters (11.5 ft). Its autapomorphies largely exist in the unique form of the process on the first wing phalanx for the extensor tendon.^[1]

Navajodactylus was tentatively assigned to the family Azhdarchidae because of its geological age, however, it does not show any synapomorphies of the group.^[1] Indeed, it may not actually be an azhdarchid, as it lacks pneumacy in its forelimb elements, which is opposed to the extensive pneumacy seen in azhdarchids.^[3]

• List of pterosaur genera
• Timeline of pterosaur research