Shrews are among the most speciose of mammalian clades, but their evolutionary history is poorly understood. Their fossil record is fragmentary and even the anatomy of living groups is not well documented. Here, we incorporate the oldest, most complete fossil shrew yet known into the first phylogenetic analysis of the group to include molecular, morphological and temporal data. Our study reveals previously unknown diversity among total- and crown-group soricids. This includes a novel element of the mammalian skeleton: a robust, needle-like sesamoid extending cranially from the second thoracic neural arch in Myosoricini, comparable in length to these species' humeri. Additionally, ‘red-toothed’ shrews have an unusually elongate basicranium, and ‘white-toothed’ shrews probably evolved from a common ancestor with dental pigmentation. The fossil Domnina and crown soricids have a double-jaw articulation and incomplete zygomatic arch, but unlike nearly all crown species, Domnina has open vomeronasal canals and a tympanic process of the basisphenoid. Domnina and other heterosoricids are phylogenetically outside crown Soricidae. The oldest, well-supported total-group soricoids are North American, not Asian, and Soricidae probably originated during the Palaeocene or early Eocene. The diverse mammalian genus Crocidura originated and began to diversify during the Miocene.