Symbiotic associations are a poorly studied aspect of the fossil record, owing largely to the taphonomic biases that inhibit direct observation that two organisms shared an intimate association in life. A symbiosis between an infesting animal and a skeleton-producing host can form a bioclaustration cavity that directly preserves the association and has a high preservation potential. Identification of ancient mutuals and parasites must reject the null hypothesis of commensalism by demonstrating that the symbiosis correlates with a positive or negative change in host fitness as compared to a non-symbiotic relative of the host taxon. Reviews of the Paleozoic record of marine symbionts show that the majority are hosted by colonial animals, especially corals and calcareous sponges. These hosts include structural forms that have moderate to high levels of integration and can support bioclaustrations between clonal units, mitigating the negative effects of symbionts, and perhaps facilitating the symbiosis. The fossil record is biased toward recording long-lasting, widespread, equilibrated associations. By contrast, parasitisms that are especially negative to the host are expected to be fossilized rarely. The symbiotic associations that form bioclaustrations may also represent an endolithic adaptive strategy in response to biological antagonisms, such as predation and spatial competition. The Late Ordovician rise in symbiotic bioclaustrations joins burrows and borings as trace fossil examples of infaunalization strategies that accompany the Ordovician faunal radiation.