The fossil record of deep-marine environments is notoriously poor in comparison with that of their shallow-marine counterparts. Notably, deep-marine deposits are typically host to diverse and abundant trace-fossil assemblages, providing evidence of the ancient deep-sea benthos. To analyze the early colonization of the deep sea, we constructed a global dataset of trace-fossil occurrences from a survey of Ediacaran–Devonian stratigraphic units. This analysis highlights the importance of the Ordovician radiation as a pivotal time in the colonization of the deep sea. Ediacaran deep-marine trace fossils consist of very simple trails and burrows. Global and alpha ichnodiversity, as well as ichnodisparity, were extremely low. Nonspecialized grazing trails reveal the exploitation of microbial mats. These strategies persisted in the Cambrian, although with an increase in ichnodiversity (both global and alpha) and ichnodisparity. An increase in the complexity of morphologic patterns, as illustrated by the undermat mining ichnogenus Oldhamia, is apparent during the Cambrian. The face of the deep sea started to change during the end of the Cambrian and beginning of the Ordovician with the protracted expansion of farming and trapping strategies. The main architectural designs of deep-marine trace fossils (e.g. regular networks, delicate spiral burrows, guided meandering graphoglyptids) were established in the deep sea by the Early Ordovician, recording the first appearance of the Nereites Ichnofacies. Lower to Middle Ordovician deep-marine ichnofaunas are moderately diverse, and fodinichnia commonly dominates rather than graphoglyptids. A significant ichnodiversity and ichnodisparity increase occurred in the Late Ordovician–early Silurian, with ichnofaunas recording higher proportions of graphoglyptids and evidencing the establishment of a deep-marine ecosystem of modern aspect. The distinction between the Nereites and Paleodictyon ichnosubfacies, with the former characterized by the dominance of feeding traces in muddy turbidites and the later by the dominance of graphoglyptids in sandy turbidites, can also be tracked back to the Ordovician radiation. This trend of increased colonization of the deep sea continued through all the Silurian and the Devonian. However, colonization of carbonate turbidites may have lagged behind that of siliciclastic turbidites. The progressive increase in abundance and diversity of graphoglyptids resulted in an increased role of gallery biodiffusers. This faunal turnover in the deep sea was coincident with an increase in oxygenation in slope and base-of-slope settings, which is thought to have been a driver of Ordovician biodiversifications. The formation of permanent open burrows in the deep sea may have increased bioirrigation in the uppermost zone of the deep-sea sediment, therefore increasing ventilation and potentially generating a feedback loop between bioturbation and oxygenation, with the endobenthos engineering its environment.