Bacterial genomes encode a plethora of small RNAs (sRNAs), which are heterogeneous in size, structure and function. Most sRNAs act as post-transcriptional regulators by means of specific base pairing interactions with the 5'-untranslated region of mRNA transcripts, thereby modifying the stability of the target transcript and/or its ability to be translated. Here, we present RNApredator, a web server for the prediction of sRNA targets. The user can choose from a set of over 2155 genomes and plasmids from 1183 bacterial species. RNApredator then uses a dynamic programming approach, RNAplex, to compute putative targets. Compared to web servers with a similar task, RNApredator takes the accessibility of the target during the target search into account, improving the specificity of the predictions. Furthermore, enrichment in Gene Ontology terms, cellular pathways as well as changes in accessibilities along the target sequence can be done in fully automated post-processing steps. The predictive performance of the underlying dynamic programming approach RNAplex is similar to that of more complex methods, but needs at least three orders of magnitude less time to complete. RNApredator is available at http://rna.tbi.univie.ac.at/RNApredator.