Plague, caused by Yersinia pestis, remains a significant public health concern, yet the determinants of many toxin-associated proteins encoded by this pathogen remain poorly understood. Here, we characterized two previously unexplored Rearrangement hotspot (Rhs) proteins, YPO3609 and YPO3615, using a combination of bioinformatic analyses, bacterial toxicity assays, DNA degradation assays, SOS reporter assays, and RT-qPCR analysis. The C-terminal domains of YPO3609 and YPO3615 confer nuclease toxicity, with YPO3609 containing a WHH motif of the HNH nuclease superfamily and YPO3615 harboring a restriction endonuclease-like aspartate dyad. Heterologous expression of these C-terminal toxin domains in Escherichia coli inhibited growth, caused DNA degradation, elicited SOS-related responses, and induced cellular filamentation. Co-expression experiments identified YPO3610 and YPO3616 as the cognate immunity proteins of YPO3609 and YPO3615, respectively, while site-directed mutagenesis further showed that H411 and D1442/D1447 contribute to the nuclease-associated activities of the two toxins. Homologs of both toxin domains were broadly distributed in Pseudomonadota, with the C-terminal domain of YPO3609 showing a wider distribution. These findings characterize two functional Rhs toxin–immunity modules encoded by Y. pestis, and provide new insights into Rhs-associated nuclease toxins and their related homologs.