We study the phylogenetic relationships of egg-brooding frogs, a group of 118 neotropical species, unique among anurans by having embryos with large bell-shaped gills and females carrying their eggs on the dorsum, exposed or inside a pouch. We assembled a total evidence dataset of published and newly generated data containing 51 phenotypic characters and DNA sequences of 20 loci for 143 hemiphractids and 127 outgroup terminals. We performed six analytical strategies combining different optimality criteria (parsimony and maximum likelihood), alignment methods (tree- and similarity-alignment), and three different indel coding schemes (fifth character state, unknown nucleotide, and presence/absence characters matrix). Furthermore, we analyzed a subset of the total evidence dataset to evaluate the impact of phenotypic characters on hemiphractid phylogenetic relationships. Our main results include: (i) monophyly of Hemiphractidae and its six genera for all our analyses, novel relationships among hemiphractid genera, and non-monophyly of Hemiphractinae according to our preferred phylogenetic hypothesis; (ii) non-monophyly of current supraspecific taxonomies of Gastrotheca, an updated taxonomy is provided; (iii) previous differences among studies were mainly caused by differences in analytical factors, not by differences in character/taxon sampling; (iv) optimality criteria, alignment method, and indel coding caused differences among optimal topologies, in that order of degree; (v) in most cases, parsimony analyses are more sensitive to the addition of phenotypic data than maximum likelihood analyses; (vi) adding phenotypic data resulted in an increase of shared clades for most analyses.