The origin and evolution of clitellate annelids—earthworms, leeches and their relatives—is poorly understood, partly because body fossils of these delicate organisms are exceedingly rare. The distinctive egg cases (cocoons) of Clitellata, however, are relatively common in the fossil record, although their potential for phylogenetic studies has remained largely unexplored. Here, we report the remarkable discovery of fossilized spermatozoa preserved within the secreted wall layers of a 50-Myr-old clitellate cocoon from Antarctica, representing the oldest fossil animal sperm yet known. Sperm characters are highly informative for the classification of extant Annelida. The Antarctic fossil spermatozoa have several features that point to affinities with the peculiar, leech-like ‘crayfish worms’ (Branchiobdellida). We anticipate that systematic surveys of cocoon fossils coupled with advances in non-destructive analytical methods may open a new window into the evolution of minute, soft-bodied life forms that are otherwise only rarely observed in the fossil record.