Ecdysozoans (Phyla Arthropoda, Kinorhyncha, Loricifera, Nematoda, Nematomorpha, Onychophora, Priapulida, Tardigrada) are invertebrates bearing a tough, periodically moulted cuticle that predisposes them to exceptional preservation. Ecdysozoans dominate the oldest exceptionally preserved bilaterian animal biotas in the early to mid-Cambrian (c. 520–508 Ma), with possible trace fossils in the latest Ediacaran (<556 Ma). The fossil record of Ecdysozoa is among the best understood of major animal clades and is believed to document their origins and evolutionary history well. Strikingly, however, molecular clock analyses have implied a considerably deeper Precambrian origin for Ecdysozoa, much older than their earliest fossils. Here, using an improved set of fossil calibrations, we performed Bayesian analyses to estimate an evolutionary time-tree for Ecdysozoa, sampling all eight phyla for the first time. Our results recover Scalidophora as the sister group to Nematoida + Panarthropoda (= Cryptovermes nov.) and suggest that the Ediacaran divergence of Ecdysozoa occurred at least 23 myr before the first potential ecdysozoan trace fossils. This finding is impervious to the use of all plausible phylogenies, fossil prior distributions, evolutionary rate models and matrix partitioning strategies. Arthropods exhibit more precision and less incongruence between fossil- and clock-based estimates of clade ages than other ecdysozoan phyla.