Morphological character analyses indicate that Rhyacichthyidae, Odontobutidae, Eleotridae, and Xenisthmidae are the basal families within the perciform suborder Gobioidei. This study uses DNA sequence data to infer the relationships of genera within these families, as well as determine the placement of more derived gobioids (family Gobiidae) and the identity of the outgroup to Gobioidei. Complete sequences of the mitochondrial ND1, ND2, COI, and cyt b genes (4397 base pairs) are analyzed for representatives of 27 gobioid genera and a variety of perciform and scorpaeniform outgroup candidates; the phylogeny is rooted with a beryciform as a distal outgroup. The single most parsimonious tree that results indicates that, of the outgroups sampled, the perciform family Apogonidae is most closely related to Gobioidei. Gobioidei is monophyletic, and Rhyacichthys aspro is the most basal taxon. The remainder of Gobioidei is resolved into clades corresponding to the families Odontobutidae (plus Milyeringa) and Eleotridae+Xenisthmidae+Gobiidae. Within Eleotridae, the subfamily Butinae (minus Milyeringa) is paraphyletic with respect to Gobiidae, and Eleotrinae is paraphyletic with respect to Xenisthmidae. Other than these groupings, the primary disagreement with the current morphology-based classification is that the molecular data indicate that the troglodytic Milyeringa should be placed in Odontobutidae, not Butinae, although support for this placement is weak. The most basal lineage of Gobioidei is known from the freshwaters of the Indo-Pacific, with marine-dwelling lineages arising several times independently in the group. The phylogeny also indicates that different gobioid lineages are distributed in Asia, Africa, Madagascar and the Neotropics. Five sister pairs of basal gobioid species inhabit Atlantic and Pacific drainages of Panama, with widely varying divergences.