Small non-coding bacterial RNAs (sRNAs) play important regulatory roles in a variety of cellular processes. Nearly all known sRNAs have been identified in Escherichia coli and most of these are not conserved in the majority of other bacterial species. Many of the E.coli sRNAs were initially predicted through bioinformatic approaches based on their common features, namely that they are encoded between annotated open reading frames and are flanked by predictable transcription signals. Because promoter consensus sequences are undetermined for most species, the successful use of bioinformatics to identify sRNAs in bacteria other than E.coli has been limited. We have created a program, sRNAPredict, which uses coordinate-based algorithms to integrate the respective positions of individual predictive features of sRNAs and rapidly identify putative intergenic sRNAs. Relying only on sequence conservation and predicted Rho-independent terminators, sRNAPredict was used to search for sRNAs in Vibrio cholerae. This search identified 9 of the 10 known or putative V.cholerae sRNAs and 32 candidates for novel sRNAs. Small transcripts for 6 out of 9 candidate sRNAs were observed by Northern analysis. Our findings suggest that sRNAPredict can be used to efficiently identify novel sRNAs even in bacteria for which promoter consensus sequences are not available.