We sequenced seven new hemerythrin (Hr) and myohemerythrin (myoHr) cDNAs from Sipunculus nudus and Golfingia vulgaris vulgaris, thus providing new comparative data that significantly increase the set of the known Hr and myoHr sequences. Bayesian inference, maximum likelihood, and maximum parsimony phylogenetic analyses were performed to investigate the evolutionary relationships among the sipunculan and annelid Hr and myoHr sequences. Annelid myoHrs and sipunculan Hrs were resolved as monophyletic groups. Conversely sipunculan myoHrs did not form a clade. The Hrs having an octameric quaternary structure were resolved as a monophyletic group. The octameric cluster includes the Hr sequences of G. v. vulgaris, Themiste zostericola, Themiste discriptum, and Phascolopsis gouldii. Siphonosoma cumanense Hr, which has a trimeric quaternary structure, assumes a sister group position of the octameric clade. The S. nudus Hrs, having a quaternary structure that is not well resolved, assume an isolate position within the Hrs clade. Likelihood-based analyses reveal that purifying selection mainly characterized the evolution of Hr and myoHr. We suggest that starting from a common gene ancestor, two distinct quaternary structures evolved in the sipunculan Hrs and this differentiation was probably favored by the acquisition of distinct physiological advantages.