Small regulatory RNAs (sRNAs) are ubiquitously present in many different bacteria and are often conserved in closely related species. The majority of the sRNAs acts as antisense RNAs via basepairing to target mRNAs and mediates up- or down-regulation. This involves effects on translation and/or mRNA stability. Since antisense-target RNA interaction sites are often short and non-contiguous, prediction of targets is a non-trivial task. Thus, most sRNA have not yet been assigned to specific target genes, and this motivates a need for computational target prediction programs. Available programs use criteria such as, for instance, a "seed" antisense-target interaction and the structural accessibility of the interaction site to indentify sRNA targets. So far, the realization that RNA/RNA interaction is a hierarchical multi-step process has not been incorporated into algorithms, and neither has conservation of interactions between related species. We have designed a target prediction program, AntisenseRNA, which considers the interaction as a multistep process, in which the intramolecular structure of the two RNAs and the phylogenetic conservation of basepairs are taken into account. AntisenseRNA successfully identifies most of the experimentally validated sRNA targets in Escherichia coli and predicts their interaction sites with high specificity and sensitivity. AntisenseRNA is about ten times faster than its best competitor programs, suggesting it to be a good choice for identification of new targets for sRNAs.