The Remipedia are enigmatic crustaceans from anchialine cave systems, first described only 30 years ago, whose phylogenetic affinities are as yet unresolved. Here we report the sequence of hemocyanin from Speleonectes tulumensis Yager, 1987 (Remipedia, Speleonectidae). This is the first proof of the presence of this type of respiratory protein in a crustacean taxon other than Malacostraca. Speleonectes tulumensis hemocyanin consists of multiple distinct (at least three) subunits (StuHc1-3; Hc, hemocyanin). Surprisingly, the sequences are most similar to hexapod hemocyanins. Phylogenetic analyses showed that the S. tulumensis hemocyanin subunits StuHc1 and StuHc3 associate with the type 1 hexapod hemocyanin subunits, whereas StuHc2 associates with the type 2 subunits of hexapods. Together, remipede and hexapod hemocyanins are in the sister-group position to the hemocyanins of malacostracan crustaceans. Hemocyanins provide no indication of a close relationship of Myriapoda and Hexapoda but support Pancrustacea (Crustacea + Hexapoda). Our results also suggest that Crustacea are paraphyletic and that Hexapoda may have evolved from a Remipedia-like ancestor. Thus, Remipedia occupy a key position for the understanding of the evolution of hexapods, which are and have been one of the world's most speciose lineage of animals.