The axial skeleton of tetrapods is organized into distinct anteroposterior regions of the vertebral column and ribs (cervical, trunk, sacral and caudal), and transitions between these regions are determined by colinear anterior expression boundaries of Hox5/6, -9, -10 and -11 paralogy group genes within embryonic paraxial mesoderm. Fishes, conversely, exhibit little in the way of discrete axial regionalization, and this has led to scenarios of an origin of Hox-mediated axial skeletal complexity with the evolutionary transition to land in tetrapods. Here, combining geometric morphometric analysis of vertebral column morphology with cell lineage tracing of hox gene expression boundaries in developing embryos, we recover evidence of at least five distinct regions in the vertebral skeleton of a cartilaginous fish, the little skate (Leucoraja erinacea). We find that skate embryos exhibit tetrapod-like anteroposterior nesting of hox gene expression in their paraxial mesoderm, and we show that anterior expression boundaries of hox5/6, hox9, hox10, and hox11 paralogy group genes predict regional transitions in the differentiated skate axial skeleton. Our findings suggest that hox-based axial skeletal regionalization did not originate with tetrapods, but rather has a much deeper evolutionary history than was previously appreciated.