Vibrio cholerae biotype El Tor is perpetuating the longest cholera pandemic in recorded history. The genomic islands VSP-1 and VSP-2 distinguish El Tor from previous pandemic V. cholerae strains. Using a co-occurrence analysis of VSP genes in >200,000 bacterial genomes we built gene networks to infer biological functions encoded in these islands. This revealed that dncV, a component of the cyclic-oligonucleotide-based anti-phage signalling system (CBASS) anti-phage defence system, co-occurs with an uncharacterized gene vc0175 that we rename avcD for anti-viral cytodine deaminase. We show that AvcD is a deoxycytidylate deaminase and that its activity is post-translationally inhibited by a non-coding RNA named AvcI. AvcID and bacterial homologues protect bacterial populations against phage invasion by depleting free deoxycytidine nucleotides during infection, thereby decreasing phage replication. Homologues of avcD exist in all three domains of life, and bacterial AvcID defends against phage infection by combining traits of two eukaryotic innate viral immunity proteins, APOBEC and SAMHD1.