The holotype specimen 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é.
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 other first phalanges were referred: TMP 72.1.1 and TMP 82.19.295, from the Dinosaur Park Formation of the Dinosaur Provincial Park, Alberta.
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.
Navajodactylus was tentatively assigned to the Azhdarchidae, because of its geological age as it does not show any synapomorphies of the group. Indeed, it may not actually be an azhdarchid, as it lacks pneumacy in its forelimb elements, as opposed to the extensive pneumacy seen in azhdarchids