Establishing well-supported monophyletic groups is a key requirement for producing a natural classification that reflects evolutionary descent. In a phylogenetic framework this is best achieved through dense taxon sampling and the analysis of a robust character dataset, combined with statistical testing of topological hypotheses. This study assesses the monophyly of tribes and subfamilies within the diverse ‘broad-nosed weevils’ (Curculionidae: Entiminae, Cyclominae and Hyperinae) through analysis of single-locus sequence data for mitochondrial cox1 and rrnL genes, in combination with a ‘backbone’ of complete and near-complete mitochondrial genome sequences. Maximum likelihood phylogenetic analyses incorporating topological constraints for various higher-taxa were statistically tested using the AU, SH, and KH tests, which indicated that three tribes within Entiminae, as presently classified, are not monophyletic. Moderate and high bootstrap support was also consistent with two entimine tribes (Peritelini and Cylydrorhinini) being each recovered as monophyletic in an unconstrained analysis. Furthermore, one genus of cyclomine weevils (Aphela) is recovered outside the clade of ‘broad-nosed weevils’, although its taxonomic placement remains uncertain. It is apparent that the present approach may be hampered by limited taxon sampling in the ‘backbone’ dataset, rendering it difficult for divergent taxa to robustly match to their closest lineages. However, with improved taxon sampling of the mitogenome tree, the general approach can be a useful taxonomic tool for weevils.