Black corals, primarily deep-sea cnidarians (Anthozoa: Antipatharia), are inferred to have originated in the Ediacaran or Cambrian based on molecular clock estimates. However, only the fossil family Sinopathidae, comprising Sinopathes and Sterictopathes, from the Early Ordovician of Hubei, China, has been recorded in the fossil record. The affinity of this family has been questioned because of morphological inconsistencies between fossil and extant species. Here we describe two transitional species of Sterictopathes from the Middle Ordovician of Shaanxi, China, bridging the fossil gaps and thereby elevating the genus Sterictopathes to a new family, Sterictopathidae fam. nov. The evolutionary trend toward regularity in the axial skeleton from the Ordovician to modern Antipatharia is highlighted by reduced ridges and longitudinal fusion of networks. This discovery and confirmation of Ordovician black corals paves the way for future fossil findings and offers new insights into the early evolution of Hexacoralia.