Hox genes exert fundamental roles for proper regional specification along the main rostro-caudal axis of animal embryos. They are generally expressed in restricted spatial domains according to their position in the cluster (spatial colinearity)—a feature that is conserved across bilaterians. In jawed vertebrates (gnathostomes), the position in the cluster also determines the onset of expression of Hox genes (a feature known as whole-cluster temporal colinearity (WTC)), while in invertebrates this phenomenon is displayed as a subcluster-level temporal colinearity. However, little is known about the expression profile of Hox genes in jawless vertebrates (cyclostomes); therefore, the evolutionary origin of WTC, as seen in gnathostomes, remains a mystery. Here, we show that Hox genes in cyclostomes are expressed according to WTC during development. We investigated the Hox repertoire and Hox gene expression profiles in three different species—a hagfish, a lamprey and a shark—encompassing the two major groups of vertebrates, and found that these are expressed following a whole-cluster, temporally staggered pattern, indicating that WTC has been conserved during the past 500 million years despite drastically different genome evolution and morphological outputs between jawless and jawed vertebrates.