Studying symbiotic interactions provides valuable insights into the ecology of extinct organisms and the broader mechanisms of evolution. Here we describe the earliest symbiotic associations between colonial corals and gastropods from the Late Ordovician of Estonia. Tabulate corals of the genus Heliolites were found in association with gastropod Ruedemannia borkholmiensis, Pachystrophia sp., and Hormotoma scorbiculata. Heliolitids encrusted only mature gastropod specimens presumably due to the need for an ample space to grow. During the Katian and Hirnantian in Estonia, gastropods provided a hard substrate for corals in areas where the seafloor was otherwise soft. The corals can use their hosts to escape unfavorable environmental conditions and withstand burial. The calcareous layer deposited by the coral strengthened the gastropod shell, making it more resilient and resistant to breakage in the event of predation by durophagous organisms or hydrodynamic events. The occurrence of the same species of gastropods and heliolitids in the Pirgu and Porkuni regional stages, independently, suggests that the symbiotic relationship between them was facultative for both partners. Taking into account the potential benefits and drawbacks involved, mutualism appears to best describe the associations between heliolitids and gastropods in the Late Ordovician of Estonia. The analysis of studied specimens suggests that corals began to colonize gastropod shells as early as the late Katian, either alive or secondarily inhabited by other invertebrates. This indicates that the innovation of coral colonization of motile gastropod shells may have emerged after the Great Ordovician Biodiversification Event (GOBE) in Baltica.