While studying organisms living in association with the solitary tunicate Phallusia nigra (Ascidiacea, Ascidiidae) from a shallow fringing reef at Zeytouna Beach (Egyptian Red Sea), one of the collected ascidians showed peculiar perforations on its tunic. Once dissected, the perforations revealed to be the openings of a network of galleries excavated in the inner tunic (atrium) by at least six individuals of a polychaetous annelid. The worms belonged to the Autolytinae (Syllidae), a subfamily that is well known to include specialized predators and/or symbionts, mostly associated with cnidarians. The Red Sea worms are here described as Proceraea exoryxae sp. nov., which are anatomically distinguished by the combination of simple chaetae only in anterior chaetigers, and a unique trepan with 33 teeth in one outer ring where one large tooth alternates with one medium-sized tricuspid tooth, and one inner ring with small teeth located just behind the large teeth. Male and female epitokes were found together with atokous individuals within galleries. Proceraea exoryxae sp. nov. constitutes the first known miner in the Autolytinae and the second species in this taxon known to live symbiotically with ascidians. The implications of finding this specialized parasite are discussed considering that Phallusia nigra has been introduced worldwide, in tropical and sub-tropical ecosystems, where it has the potential of becoming invasive.