A phylogeny is presented for the western Palaearctic representatives of the weevil subfamily Cryptorhynchinae using a combination of phenotypic and genotypic characters. This phylogeny is the first for the extremely species-rich Cryptorhynchinae to use molecular data (mitochondrial CO1 and 16S as well as nuclear ribosomal 28S). The results of this study show the need for molecular tools within this morphologically cryptic group of weevils and provide a scaffold based on which genus assignment can be tested. The present study mostly corroborates the current subdivision into genera (but many of the subgeneric groups are questioned). Three new genera are described: Montanacalles gen. nov. (type species: Kyklioacalles nevadaensis Stüben, 2001), Coloracalles gen. nov. (type species: Acalles humerosus Fairmaire, 1862) and Elliptacalles gen. nov. (type species: Acalles longus Desbrochers, 1892). Relevant external characters and the male genitalia of all discussed taxa are illustrated. Three species are transferred to different genera: Kyklioacalles aubei (Boheman, 1837) (formerly: Acalles), Ruteria major (Solari A. & F., 1907) and Ruteria minosi (Bahr & Bayer, 2005) (both formerly Echinodera).