The genus Brachycephalus is a fascinating group of miniaturized anurans from the Brazilian Atlantic Forest, comprising the conspicuous, brightly colored pumpkin-toadlets and the cryptic flea-toads. Pumpkin-toadlets are known to contain tetrodotoxins and therefore, their bright colors may perform an aposematic function. Previous studies based on a limited number of mitochondrial and nuclear-encoded markers supported the existence of two clades containing species of pumpkin-toadlet phenotype, but deep nodes remained largely unresolved or conflicting between data sets. We use new RNAseq data of 17 individuals from nine Brachycephalus species to infer their evolutionary relationships from a phylogenomic perspective. Analyses of almost 5300 nuclear-encoded ortholog protein-coding genes and full mitochondrial genomes confirmed the existence of two separate pumpkin-toadlet clades, suggesting the convergent evolution (or multiple reversals) of the bufoniform morphology, conspicuous coloration, and probably toxicity. In addition, the study of the mitochondrial gene order revealed that three species (B. hermogenesi, B. pitanga, and B. rotenbergae) display translocations of different tRNAs (NCY and CYA) from the WANCY tRNA cluster to a position between the genes ATP6 and COIII, showing a new mitochondrial gene order arrangement for vertebrates. The newly clarified phylogeny suggests that Brachycephalus has the potential to become a promising model taxon to understand the evolution of coloration, body plan and toxicity. Given that toxicity information is available for only few species of Brachycephalus, without data for any flea-toad species, we also emphasize the need for a wider screening of toxicity across species, together with more in-depth functional and ecological study of their phenotypes.