Background: Hemocyanin transports O-2 in the hemolymph of many arthropod species. Such respiratory proteins have long been considered unnecessary in Myriapoda. As a result, the presence of hemocyanin in Myriapoda has long been overlooked. We analyzed transcriptome and genome sequences from all major myriapod taxa - Chilopoda, Diplopoda, Symphyla, and Pauropoda - with the aim of identifying hemocyanin-like proteins. Results: We investigated the genomes and transcriptomes of 56 myriapod species and identified 46 novel full-length hemocyanin subunit sequences in 20 species of Chilopoda, Diplopoda, and Symphyla, but not Pauropoda. We found in Cleidogona sp. (Diplopoda, Chordeumatida) a hemocyanin-like sequence with mutated copper-binding centers, which cannot bind O-2. An RNA-seq approach showed markedly different hemocyanin mRNA levels from similar to 6 to 25,000 reads per kilobase per million reads. To evaluate the contribution of hemocyanin to O-2 transport, we specifically studied the hemocyanin of the centipede Scolopendra dehaani. This species harbors two distinct hemocyanin subunits with low expression levels. We showed cooperative O-2 binding in the S. dehaani hemolymph, indicating that hemocyanin supports O-2 transport even at low concentration. Further, we demonstrated that hemocyanin is > 1500-fold more highly expressed in the fertilized egg than in the adult. Conclusion: Hemocyanin was most likely the respiratory protein in the myriapod stem-lineage, but multiple taxa may have independently lost hemocyanin and thus the ability of efficient O-2 transport. In myriapods, hemocyanin is much more widespread than initially appreciated. Some myriapods express hemocyanin only at low levels, which are, nevertheless, sufficient for O-2 supply. Notably, also in myriapods, a non-respiratory protein similar to insect storage hexamerins evolved from the hemocyanin.