Holasteroids are a major clade of irregular echinoids that today is confined to the deep-sea, but which has a rich fossil record extending back to the start of the Cretaceous Period. A cladistic analysis of this clade, encompassing the great majority of living and fossil genera, is undertaken based on new data on test architecture. The classification of the group is reviewed and a new hierarchical scheme is proposed. The highly atypical apical disc structure of pourtalesiid holasteroids is discussed and critical data for understanding its plate homologies are provided by the most primitive pourtalesiid, the Late Cretaceous Galeaster. This supports the idea that plates previously identified as posterior genital plates in pourtalesiids are in fact ocular plates II and IV. An evolutionary tree for holasteroids is constructed by calibrating the cladogram against the stratigraphic record. This is then used to examine how holasteroid diversity and ecology have changed through time. Holasteroids have migrated into the deep-sea at least four times independently. Three of these lineages can be traced back to sister taxa living in deep-water continental shelf environments in the Late Cretaceous-early Tertiary, while a fourth represents a very much younger migration event, possibly Late Miocene in age.