Its remains were collected but not prepared by Barnum Brown in 1918, from rocks better known for their fossils of marine life. When seven black chalkstone blocks were prepared from 1966 by Richard Lund by dissolving the substrate in acid, this revealed the remains of a pterosaur. Ned Colbert described and named the genus in 1969. The type species is Nesodactylus hesperius. The genus name is derived from Greek nesos, "island" and daktylos, "finger", a reference to the island of Cuba and the typical wing finger of pterosaurs. The specific name means "western", from Greek hesperios.