Hexamerins are large storage proteins of insects in the 500 kDa range that evolved from the copper-containing hemocyanins. Hexamerins have been found at high concentration in the hemolymph of many insect taxa, but have remained unstudied in relatively basal taxa. To obtain more detailed insight about early hexamerin evolution, we have studied hexamerins in stoneflies (Plecoptera). Stoneflies are also the only insects for which a functional hemocyanin is known to co-occur with hexamerins in the hemolymph. Here, we identified hexamerins in five plecopteran species and obtained partial cDNA sequences from Perla marginata (Perlidae), Nemoura sp. (Nemouridae), Taeniopteryx burksi (Taeniopterygidae), Allocapnia vivipara (Capniidae), and Diamphipnopsis samali (Diamphipnoidae). At least four distinct hexamerins are present in P. marginata. The full-length cDNA of one hexamerin subunit was obtained (PmaHex1) that measures 2475 bp and translates into a native polypeptide of 702 amino acids. Phylogenetic analyses showed that the plecopteran hexamerins are monophyletic and positioned at the base of the insect hexamerin tree, probably diverging about 360 million years ago. Within the Plecoptera, distinct hexamerin types evolved before the divergence of the families. Mapping amino acid compositions onto the phylogenetic tree shows that the accumulation of aromatic amino acids (and thus the evolution of "arylphorins") commenced soon after the hexamerins diverged from hemocyanins, but also indicates that hexamerins with distinct amino acid compositions reflect secondary losses of aromatic amino acids.