Parasite-host systems are pervasive in nature but are extremely difficult to convincingly identify in the fossil record. Here we report quantitative evidence of parasitism in the form of a unique, enduring life association between tube-dwelling organisms encrusted to densely clustered shells of a monospecific organophosphatic brachiopod assemblage from the lower Cambrian (Stage 4) of South China. Brachiopods with encrusting tubes have decreased biomass (indicating reduced fitness) compared to individuals without tubes. The encrusting tubes orient tightly in vectors matching the laminar feeding currents of the host, suggesting kleptoparasitism. With no convincing parasite-host interactions known from the Ediacaran, this widespread sessile association reveals intimate parasite-host animal systems arose in early Cambrian benthic communities and their emergence may have played a key role in driving the evolutionary and ecological innovations associated with the Cambrian radiation.