We have characterized the sperm nuclear basic proteins (SNBPs) of the sticklebacks in the suborder Gasterosteoidei. The complete amino acid sequence of the protamines from Aulorhynchus flavidus, Pungitius pungitius, Gasterosteus aculeatus, (anadromous) and G. wheatlandi, as well as the sequences of the protamines of several species pairs of freshwater G. aculeatus, have been determined. Analysis of the primary structure of these proteins has shown that: a) despite the relatively low amino acid complexity and small molecular mass of these basic proteins, they are very good molecular markers at the generic level. The bootstrap parsimony analysis using their sequences provides a phylogenetic relationship for the old anadromous species of Gasterosteoidei which is identical to that obtained from morphological and behavioral analysis; b) the comparison of the sequences also suggests that protamines from the suborder Gasterosteoidei have most likely evolved from a common gene in the early Acanthopterygii by an extension of the carboxy terminal portion of the molecule; c) protamines are not good markers for recent postglacial freshwater isolates of G. aculeatus. However, in the unique case of Enos Lake (British Columbia), we have been able to detect an additional minor protamine component in the benthic forms of G. aculeatus that is not present in the limnetic forms. Thus, this new protamine must have appeared during the past 12,000 years concomitantly with the speciation of benthics and limnetics in this lake. Mol. Reprod. Dev. 57:185–193, 2000. © 2000 Wiley-Liss, Inc.