Here, we report the earliest fossil record to our knowledge of surface fouling by aggregates of small vermiform, encrusting and annulated tubular organisms associated with a mobile, nektonic host, the enigmatic Cambrian animal Vetulicola. Our material is from the exceptionally preserved early Cambrian (Epoch 2, Age 3), Chengjiang biota of Yunnan Province, southwest China, a circa 518 million-year old marine deposit. Our data show that symbiotic fouling relationships between species formed a component of the diversification of animal-rich ecosystems near the beginning of the Phanerozoic Eon, suggesting an early escalation of intimate ecologies as part of the Cambrian animal radiation.