The degree to which evolutionary outcomes are historically contingent remains unresolved, with studies at different levels of the biological hierarchy reaching different conclusions. Here we examine historical contingency in the origin of two evolutionary novelties in bryozoans, a phylum of colonial animals whose fossil record is as complete as that of any major group. In cheilostomes, the dominant living bryozoans, key innovations were the costal shield and ascus, which first appeared in the Cretaceous 85-95 Myr ago. We establish the parallel origin of these structures less than 12 Myr ago in an extant bryozoan genus, Cauloramphus, with transitional stages remarkably similar to those inferred for a Cretaceous clade. By one measure, long lag times in the first origins of costal shield and ascus suggest a high degree of historical contingency. This, however, does not equate with dependence on a narrow set of initial conditions or a low probability of evolution. More than one set of initial conditions may lead to an evolutionary outcome, and alternative sets are not entirely independent. We argue that, although historically contingent, the origin of ascus and costal shield was highly likely with sufficient possibilities afforded by time.