The prediction of pairing between microRNAs (miRNAs) and the miRNA recognition elements (MREs) on mRNAs is expected to be an important tool for understanding gene regulation. Here, we show that mRNAs that contain Pumilio recognition elements (PRE) in the proximity of predicted miRNA-binding sites are more likely to form stable secondary structures within their 3'-UTR, and we demonstrated using a PUM1 and PUM2 double knockdown that Pumilio proteins are general regulators of miRNA accessibility. On the basis of these findings, we developed a computational method for predicting miRNA targets that accounts for the presence of PRE in the proximity of seed-match sequences within poorly accessible structures. Moreover, we implement the miRNA-MRE duplex pairing as a two-step model, which better fits the available structural data. This algorithm, called MREdictor, allows for the identification of miRNA targets in poorly accessible regions and is not restricted to a perfect seed-match; these features are not present in other computational prediction methods.