We identified Oligoribonuclease (Orn), an essential Escherichia coli protein and the only exonuclease degrading small ribonucleotides (5mer to 2mer) and its human homologue, small fragment nuclease (Sfn), in a screen for proteins that are potentially regulated by 3'-phosphoadenosine 5'-phosphate (pAp). We show that both enzymes are sensitive to micromolar amounts of pAp in vitro. We also demonstrate that Orn can degrade short DNA oligos in addition to its activity on RNA oligos, similar to what was documented for Sfn. pAp was shown to accumulate as a result of inhibition of the pAp-degrading enzyme by lithium, widely used to treat bipolar disorder, thus its regulatory targets are of significant medical interest. CysQ, the E.coli pAp-phosphatase is strongly inhibited by lithium and calcium in vitro and is a main target of lithium toxicity in vivo. Our findings point to remarkable conservation of the connection between sulfur- and RNA metabolism between E.coli and humans.