Small RNAs (sRNAs) are a growing class of non-protein-coding transcripts that participate in the regulation of virtually every aspect of bacterial physiology. Heterocystous cyanobacteria are a group of photosynthetic organisms that exhibit multicellular behavior and developmental alternatives involving specific transcriptomes exclusive of a given physiological condition or even a cell type. In the context of our ongoing effort to understand developmental decisions in these organisms we have undertaken an approach to the global identification of sRNAs. Using differential RNA-Seq we have previously identified transcriptional start sites for the model heterocystous cyanobacterium Nostoc sp. PCC 7120. Here we combine this dataset with a prediction of Rho-independent transcriptional terminators and an analysis of phylogenetic conservation of potential sRNAs among 89 available cyanobacterial genomes. In contrast to predictive genome-wide approaches, the use of an experimental dataset comprising all active transcriptional start sites (differential RNA-Seq) facilitates the identification of bona fide sRNAs. The output of our approach is a dataset of predicted potential sRNAs in Nostoc sp. PCC 7120, with different degrees of phylogenetic conservation across the 89 cyanobacterial genomes analyzed. Previously described sRNAs appear among the predicted sRNAs, demonstrating the performance of the algorithm. In addition, new predicted sRNAs are now identified that can be involved in regulation of different aspects of cyanobacterial physiology, including adaptation to nitrogen stress, the condition that triggers differentiation of heterocysts (specialized nitrogen-fixing cells). Transcription of several predicted sRNAs that appear exclusively in the genomes of heterocystous cyanobacteria is experimentally verified by Northern blot. Cell-specific transcription of one of these sRNAs, NsiR8 (nitrogen stress-induced RNA 8), in developing heterocysts is also demonstrated.