DNA deaminase toxins are involved in interbacterial antagonism and the generation of genetic diversity in surviving bacterial populations. These enzymes have also been adopted as genome engineering tools. The single-stranded (ss)DNA deaminase SsdA represents the bacterial deaminase toxin family-2 (BaDTF2) and it deaminates ssDNA cytosines with little sequence context dependence, which contrasts with the AID/APOBEC family of sequence-selective ssDNA cytosine deaminases. Here we report the crystal structure of SsdA in complex with a ssDNA substrate. The structure reveals a unique mode of substrate binding, in which a cluster of aromatic residues of SsdA engages ssDNA in a V-shaped conformation sharply bent across the target cytosine. The bases 5' or 3' to the target cytosine are stacked linearly and make few sequence-specific protein contacts, thus explaining the broad substrate selectivity of SsdA. Unexpectedly, SsdA contains a β-amino acid isoaspartate, which is important for enzymatic activity and may contribute to the stability of SsdA as a toxin. Structure- function studies helped to design SsdA mutants active in human cells, which could lead to future applications in genome engineering.