Hfq-binding small RNAs (sRNAs) in bacteria modulate the stability and translational efficiency of target mRNAs through limited base-pairing interactions. While these sRNAs are known to regulate numerous mRNAs as part of stress responses, what distinguishes targets and non-targets among the mRNAs predicted to base pair with Hfq-binding sRNAs is poorly understood. Using the Hfq-binding sRNA Spot 42 of Escherichia coli as a model, we found that predictions using only the three unstructured regions of Spot 42 substantially improved the identification of previously known and novel Spot 42 targets. Furthermore, increasing the extent of base-pairing in single or multiple base-pairing regions improved the strength of regulation, but only for the unstructured regions of Spot 42. We also found that non-targets predicted to base pair with Spot 42 lacked an Hfq-binding site, folded into a secondary structure that occluded the Spot 42 targeting site, or had overlapping Hfq-binding and targeting sites. By modifying these features, we could impart Spot 42 regulation on non-target mRNAs. Our results thus provide valuable insights into the requirements for target selection by sRNAs.