The monophyletic group Caniformia in the order Carnivora currently comprises seven families whose relationships remain contentious. The phylogenetic positions of the two panda species within the Caniformia have also been evolutionary puzzles over the past decades, especially for Ailurus fulgens (the red panda). Here, new nuclear sequences from two introns of the β-fibrinogen gene (β-fibrinogen introns 4 and 7) and a complete mitochondrial (mt) gene (ND2) from 17 caniform representatives were explored for their utilities in resolving higher-level relationships in the Caniformia. In addition, two previously available nuclear (IRBP exon 1 and TTR intron 1) data sets were also combined and analyzed simultaneously with the newly obtained sequence data in this study. Combined analyses of four nuclear and one mt genes (4417 bp) recover a branching order in which almost all nodes were strongly supported. The present analyses provide evidence in favor of Ailurus fulgens as the closest taxon to the procyonid-mustelid (i.e., Musteloidea sensu stricto) clade, followed by pinnipeds (i.e., Otariidae and Phocidae), Ursidae (including Ailuropoda melanoleuca), and Canidae, the most basal lineage in the Caniformia. The potential utilities of different genes in the context of caniform phylogeny were also evaluated, with special attention to the previously unexplored β-fibrinogen intron 4 and 7 genes.