Cerradomys is a Neotropical genus of cricetid rodents with seven recognized species, Cerradomys subflavus, C. maracajuensis, C. marinhus, C. scotti, C. langguthi, C. vivoi, and C. goytaca. Species of the genus are distributed throughout the open vegetation belt across South America, from northeastern and southeastern Atlantic coast of Brazil to eastern Paraguay and Western Bolivia. Here we describe a new species of Cerradomys from the state of Tocantins in Central Brazil, based on morphological, karyological and mitochondrial DNA analyses. This species is characterized by a medium body size and long tail, dense dorsal pelage, overall dorsal color gray olive lined with yellow, color of head and dorsum continuous, ventral body color slightly yellowish, skull with deep rostral depression, mesopterygoid fossa with long and wide sphenopalatine vacuities, presence of alisphenoid strut and of complex posterolateral palatal pits, and a unique chromosomal formula (2n = 60 and FNa = 74). Phylogenetic analyses based on cytochrome b sequences, including for the first time all known Cerradomys species, indicate that the new species is more closely related to C. scotti. The new species is found in sympatry with C. marinhus, while C. marinhus, C. scotti, and C. subflavus are found in sympatry (but not in syntopy) in one locality in the state of Minas Gerais. Finally, analysis of cytochrome b sequences indicates that C. subflavus and C. goytaca are very closely related genetically and might be conspecific. Alternatively, these results can also be explained by incomplete lineage sorting due to a recent speciation event.