Bacterial Hfq proteins facilitate interactions between mRNAs and sRNAs that regulate expression of stress response genes at the post-transcriptional level. While the formation of Hfq-RNA complexes is required for this function, the RNA-binding mechanism and Hfq residues involved in binding RNA are not well understood. To identify Hfq residues likely to interact with RNA, a two-step approach was used. The ‘Q-Site Finder' detection algorithm was applied to the E. coli Hfq structure to predict Hfq surface regions likely to interact with RNA. These regions were further explored by utilizing Affinity molecular modeling software to dock an A4 molecule to the predicted Hfq binding regions. Energy minimization followed by simulated annealing produced multiple low energy A4-Hfq complexes. Parsing the interactions of the low energy complexes revealed residues involved in binding A4 as well as the types of interaction. Seven amino acids were observed to be frequently involved in RNA binding on the proximal side, including F42, Y55, and H57. Eight residues were frequently observed on the distal side, including Y25,I30 and K31, and eleven residues on the edge surface. A number of predicted residues on the proximal side correspond very well with residues identified in the crystal structure of an Hfq-AU5G complex. Several residues identified on the distal surface (Y25, I30 and K31) were experimentally shown to affect E. coli Hfq binding to An oligomers. Results from this modeling study can guide rational mutagenesis aimed at elucidating the residues of E. coli Hfq involved in RNA binding.