In addition to its well-established defense function, CRISPR/Cas can also exhibit crucial non-canonical activity through endogenous gene expression regulation, which was found to mainly affect bacterial virulence. These non-canonical functions depend on scaRNA, which is a small RNA encoded outside of CRISPR array, that is typically flanked by a transcription start site (TSS) and a terminator, and is in part complementary to another small CRISPR/Cas-associated RNA (tracrRNAs). Identification of scaRNAs is however largely complicated by the scarcity of RNA-Seq data across different bacteria, so that they were identified only in a relatively rare CRISPR/Cas subtype (IIB), and the possibility of finding them in other Type II systems is currently unclear. This study presents the first effort toward systematic detection of small CRISPR/Cas-associated regulatory RNAs, where obtained predictions can guide future experiments. The core of our approach is ab initio detection of small RNAs from bacterial genome, which is based on jointly predicting transcription signals - TSS and terminators - and homology to CRISPR array repeat. Particularly, we employ our improved approach for detecting bacterial TSS, since accurate TSS detection is the main limiting factor for accurate small RNA prediction. We also explore how our predictions match to available RNA-Seq data and analyze their conservation across related bacterial species. In Type IIB systems, our predictions are consistent with experimental data, and we systematically identify scaRNAs throughout this subtype. Furthermore, we identify scaRNA:tracrRNA pairs in a number of IIA/IIC systems, where the appearance of scaRNAs co-occurs with the strains being pathogenic. RNA-Seq and conservation analysis show that our method is well suited for predicting CRISPR/Cas-associated small RNAs. We also find possible existence of a modified mechanism of CRISPR-associated small RNA action, which, interestingly, closely resembles the setup employed in biotechnological applications. Overall, our findings indicate that scaRNA:tracrRNA pairs are present in all subtypes of Type II systems, and point to an underlying connection with bacterial virulence. In addition to formulating these hypotheses, careful manual curation that we performed, makes an important first step toward fully automated predictor of CRISPR/Cas-associated small RNAs, which will allow their large scale analysis across diverse bacterial genomes.