The Gasterosteidae is an important model system in evolutionary biology. Phylogenetic relationships have previously been constructed based upon morphological and behavioral data, but to date no one has investigated those relationships using molecular characters. This paper reports the results of an analysis using sequences from five mitochondrial genes (12S rRNA, 16S rRNA, cytochrome b, ATPase 6, and control region). Phylogenetic analysis of 2879 bp produced a single most parsimonious tree with a consistency index of 72.6%. That tree agrees with the behavior+morphology topology, with one exception: Apeltes is placed as the sister group to Pungitius+Culaea, rather than as the sister-group of (Pungitius+Culaea)+Gasterosteus. This study highlights the importance of using multiple mitochondrial genes in a phylogenetic analysis. Separately, the five genes produced four significantly different topologies, and might have given different versions of gasterosteid relationships had only one or two genes been sequenced. It is thus imperative that comparative biologists choose only trees that contain multiple mitochondrial genes as the basis for studies of evolutionary patterns and processes.