Gobioidei is one of the largest suborders of teleost fishes, with nearly 2000 extant species currently recognized. They have a worldwide distribution and show a spectacular variety in morphology, ecology, and behavior. Despite their importance, phylogenetic relationships among many groups of gobioids (including some of the major lineages) still remain poorly understood. In this study, we analyze sequence data of five molecular markers (two mitochondrial and three nuclear) averaging 6000 bp for 222 species of gobioids. Our study is the first to include both multiple nuclear and mitochondrial genes to reconstruct a comprehensive multilocus phylogeny of gobioids encompassing most major lineages representing the overall diversity of one of the most speciose vertebrate lineages. Two separate datasets are produced and used to specifically address the phylogenetic placement of Rhyacichthyidae and Odontobutidae, and the phylogenetic relationships among gobioid lineages. Our results strongly support that the initial split in the gobioid tree separated a clade containing Rhyacichthyidae+Odontobutidae as the sister group of all other lineages. The family Eleotrididae branches off the gobioid tree after the Rhyacichthyidae+Odontobutidae clade, followed by the Butidae as sister group to the Gobiidae. Additionally, several major monophyletic groups are confidently identified within the two major Gobiidae subclades, the gobiine-like gobiids and the gobionelline-like gobiids. Robustness of the phylogenetic trees inferred here is significantly higher than that of previous studies, hence our results provide the most compelling molecular phylogenetic hypothesis of Gobioidei thus far. For the first time, we provide a comprehensive sampling of European gobies that traditionally have been divided into "transverse" gobies and "sand gobies". We show that the European gobies cluster in three distinct lineages, the Pomatoschistus-, Aphia-, and Gobius-lineages. The former resolved within the gobionelline-like gobiids and the latter two within the gobiine-like gobiids. These findings have significant implications for our understanding of the phylogeographic origin of European gobies in the light of the closure of the Paratethys. A rogue taxon analysis identified Kraemeria as an unstable taxon decreasing support at the base of the gobiine-like gobiids. Removal of this rogue taxon significantly increased phylogenetic resolution in that part of the tree and revealed additional insights into early bursts of cladogenesis of the gobiine-like gobiids.