In response to nitrogen deficiency, some cyanobacteria develop heterocysts, a terminally differentiated cell type, specialized for the fixation of atmospheric nitrogen. In Nostocales, this differentiation process is controlled by two major regulators, NtcA and HetR, but additional unknown factors are likely to be involved as well. In the context of a genome-wide search for potential non-coding RNAs, we identified an array of 12 tandem repeats that is transcribed in large amounts when cells enter conditions that trigger cell differentiation and switch to nitrogen fixation. The main accumulating transcript, which we suggest designating nitrogen stress-induced RNA 1 (NsiR1), has properties similar to regulatory non-coding RNAs. In Anabaena sp. PCC 7120, it is about 60 nt in length, has a very distinct predicted secondary structure, and is expressed very early and transiently after nitrogen step-down. Moreover, its expression requires HetR and NtcA and is restricted to cells that are differentiating into heterocysts, clearly placing NsiR1 within the regulon that controls the switch to nitrogen fixation and heterocyst formation. The genomic arrangement of NsiR1, located upstream of hetF, a gene whose product is involved in heterocyst formation, is conserved in all five Nostocales whose genomes are completely sequenced. Additionally, we detected NsiR1 expression in 19 different heterocyst-forming cyanobacteria. Our data suggest that every repeat is a complete transcriptional unit furnished with a cell-type-specific promoter and a Rho-independent terminator, which gives rise to a very high NsiR1 transcript level. NsiR1 is the first known bacterial non-coding RNA that is specifically upregulated in response to nitrogen step-down.