An alternative adaptive-immune system is present in the most basal vertebrates--lampreys and hagfish--the only surviving jawless vertebrates. These eel-like fish use leucine-rich repeat-based receptors for Ag recognition instead of the Ig-based receptors used in jawed vertebrates. We report that in Japanese lamprey (Lampetra japonica), variable lymphocyte receptor (VLR)B interacts with C1q and C3 proteins to mediate complement-dependent cytotoxicity for bacteria and tumor cells. The immune-based lysis involves deposition of VLRB and C1q-like protein complex on the surface of target cells, activation of C3, and ultimate disruption of cell wall integrity. The demonstration of functional interaction between VLRB and complement components in lamprey provides evidence for the emergence of cooperative innate and adaptive-immune responses at a pivotal point in vertebrate evolution, before or in parallel with the evolution of Ig-based Abs and the classical complement-activation pathway.