Symbiotic relationships are widespread in terrestrial and aquatic animals today, but evidence of symbiosis in the fossil record between soft-bodied bilaterians where the symbiont is intimately associated with the integument of the host is extremely rare. The radiation of metazoan life apparent in the Ediacaran (~635-541 million years ago) and Cambrian (~541-488 million years ago) periods is increasingly accepted to represent ecological diversification resulting from earlier key genetic developmental events and other innovations that occurred in the late Tonian and Cryogenian periods (~850-635 million years ago). The Cambrian has representative animals in each major ecospace category, the early Cambrian in particular having witnessed the earliest known complex animal communities and trophic structures, including symbiotic relationships. Here we report on newly discovered Cricocosmia and Mafangscolex worms that are hosts to aggregates of a new species of tiny worm in the lower Cambrian (Series 2, Stage 3) Chengjiang Lagerstätte of Yunnan Province, southwest China. The worm associations suggest the earliest known record of aggregate infestation of the integument of a soft-bodied bilaterian, host specificity and host shift.