Abstract Motivation: Regulatory RNAs often unfold their action via RNA-RNA interaction. Transcriptional gene silencing by means of siRNAs and miRNA as well as snoRNA directed RNA editing rely on this mechanism. Additionally ncRNA regulation in bacteria is mainly based upon RNA duplex formation. Finding putative target sites for newly discovered ncRNAs is a lengthy task as tools for cofolding RNA molecules like RNAcofold and RNAup are too slow for genome-wide search. Tools like RNAhybrid that neglects intramolecular interactions have runtimes proportional to 𝒪(m · n), albeit with a large prefactor. Still in many cases the need for even faster methods exists. Results: We present a new program, RNAplex, especially designed to quickly find possible hybridization sites for a query RNA in large RNA databases. RNAplex uses a slightly different energy model which reduces the computational time by a factor 10–27 compared to RNAhybrid. In addition a length penalty allows to focus the target search on short highly stable interactions. Availability: RNAplex can be downloaded at http://www.tbi.univie.ac.at/~htafer/ Contact: ivo@tbi.univie.ac.at Supplementary information: Supplementary data are available at Bioinformatics online.