Many small, noncoding RNAs in bacteria act as post-transcriptional regulators by basepairing with target mRNAs. While the number of characterized small RNAs (sRNAs) has steadily increased, only a limited number of the corresponding mRNA targets have been identified. Here we present a program, TargetRNA, that predicts the targets of these bacterial RNA regulators. The program was evaluated by assessing whether previously known targets could be identified. The program was then used to predict targets for the Escherichia coli RNAs RyhB, OmrA, OmrB and OxyS, and the predictions were compared with changes in whole genome expression patterns observed upon expression of the sRNAs. Our results show that TargetRNA is a useful tool for finding mRNA targets of sRNAs, although its rate of success varies between sRNAs.