Bacterial small ribonucleic acids (sRNAs) that are not ribosomal and transfer or messenger RNAs were initially identified in the sixties, whereas their molecular functions are still under active investigation today. It is now widely accepted that most play central roles in gene expression regulation in response to environmental changes. Interestingly, some are also implicated in bacterial virulence. Functional studies revealed that a large subset of these sRNAs act by an antisense mechanism thanks to pairing interactions with dedicated mRNA targets, usually around their translation start sites, to modulate gene expression at the posttranscriptional level. Some sRNAs modulate protein activity or mimic the structure of other macromolecules. In the last few years, in silico methods have been developed to detect more bacterial sRNAs. Among these, computational analyses of the bacterial genomes by comparative genomics have predicted the existence of a plethora of sRNAs, some that were confirmed to be expressed in vivo. The prediction accuracy of these computational tools is highly variable and can be perfectible. Here we review the computational studies that have contributed to detecting the sRNA gene and mRNA targets in bacteria and the methods for their experimental testing. In addition, the remaining challenges are discussed.