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é.[1]