The ecologically important cyanobacterium Prochlorococcus possesses the smallest genome among oxyphototrophs, with a reduced suite of protein regulators and a disproportionately high number of regulatory RNAs. Many of these are asRNAs, raising the question whether they modulate gene expression through the protection of mRNA from RNase E degradation. To address this question, we produced recombinant RNase E from Prochlorococcus sp. MED4, which functions optimally at 12 mM Mg(2+), pH 9 and 35°C. RNase E cleavage assays were performed with this recombinant protein to assess enzyme activity in the presence of single- or double-stranded RNA substrates. We found that extraordinarily long asRNAs of 3.5 and 7 kb protect a set of mRNAs from RNase E degradation that accumulate during phage infection. These asRNA-mRNA duplex formations mask single-stranded recognition sites of RNase E, leading to increased stability of the mRNAs. Such interactions directly modulate RNA stability and provide an explanation for enhanced transcript abundance of certain mRNAs during phage infection. Protection from RNase E-triggered RNA decay may constitute a hitherto unknown regulatory function of bacterial cis-asRNAs, impacting gene expression.