Major crown-groups of rodents were well established in the early Tertiary, and fossils provide an invaluable window into their evolutionary history. The main focus of this project was to perform a cladistic assessment of the dental evidence for early Tertiary rodent cladogenesis – the masticatory apparatus and teeth are the most frequently preserved anatomical features in the fossil record. We focused on groups that existed in a period corresponding to their early history, combining fossils belonging to extinct lineages and to stem-groups leading to modern lineages. While the monophyly of some groups is not systematically explored, our results have important implications for high-level rodent relationships and systematics. These results are consistent with those of recent molecular phylogenies and reliably congruent with the stratigraphic record, thus enhancing the pertinence of dental characters for phylogenetic inference. Our approach provides evidence of a fundamental dichotomy in early rodent history. Two major clades have been identified: (1) the earliest ‘ctenodactyloid’ (Ctenodactylidae, Chapattimyidae, Yuomyidae, Diatomyidae) and hystricognathous (Tsaganomyidae, Baluchimyinae, ‘phiomorphs’, ‘caviomorphs’) rodents, and (2) the earliest ‘ischyromyoid’ rodents with their closest relatives (Muroidea + Dipodoidea + Geomyoidea + Anomaluroidea + Castoroidea + Sciuravidae + Gliroidea, and Sciuroidea + Aplodontoidea + Theridomorpha). This topology has led us to endorse Ctenohystrica as the first clade and propose a new taxon, Ischyromyiformes, for the second. Although minimized in our working hypothesis, the homoplasy in dental characters remains significant. However, a number of homoplasic characters reveal structuring in their internal distribution, allowing us to discern evolutionary morphological patterns, notably the pentalophodonty of molars, zygomasseteric complex and incisor enamel microstructure. © 2004 The Linnean Society of London, Zoological Journal of the Linnean Society, 2004, 142, 105–134.