Fossil remains from the early Cambrian Period suggest an ancient origin for the phylum Chaetognatha. As macrofossils, Cambrian chaetognaths are restricted to just a few Konservat-Lagerst & auml;tten sites, yet the dispersed grasping spines characteristic of this clade are relatively common as phosphatized 'protoconodonts'. Here, an abundance of protoconodonts are described, but preserved in an entirely different manner, as 'small carbonaceous fossils' (SCFs) extracted from Cambrian Fortunian and Stage 4 mudrocks of Estonia and Sweden, respectively. Preservation among small carbonaceous fossils is substantial, representing an alternative but overlooked resource for tracing the origins of the chaetognath clade. Importantly, small carbonaceous fossils are abundant in normal marine siliciclastic deposits, in which conventionally studied phosphatic protoconodont fossils are scarce. Recent advances in constraining the phylogenetic position of chaetognaths suggest a relationship to the clade Gnathifera (gnathostomulids, micrognathozoans, rotifers). Newly emerging small carbonaceous fossil records, therefore, offer the chance to establish important calibration points for the divergence of deep bilaterian clades, including Protostomia, Lophotrochozoa and Gnathifera. Protoconodonts are especially valuable in this respect given their appearance close to, or prior to, the Ediacaran-Cambrian boundary. A first compilation of small carbonaceous fossil protoconodont records suggests chaetognath-like bilaterians had evolved by the latest Ediacaran (approximately 555-545 Ma), while the jaw complex possessed by the chaetognath crown-group emerged at least 520 Ma.