Flaviviruses such as the dengue (DENV) and the Zika virus (ZIKV) are important human pathogens causing around 100 million symptomatic infections each year. During infection, small subgenomic flavivirus RNAs (sfRNAs) are formed inside the infected host cell as a result of incomplete degradation of the viral RNA genome by cellular exoribonuclease XRN1. Although the full extent of sfRNA functions is to be revealed, these non-coding RNAs are key virulence factors and their detrimental effects on multiple cellular processes seem to consistently involve molecular interactions with RNA-binding proteins (RBPs). Discovery of such sfRNA-binding host-factors has followed established biochemical pull-down approaches skewed towards highly abundant proteins hampering proteome-wide coverage. Yeast three-hybrid (Y3H) systems represent an attractive alternative approach. To facilitate proteome-wide screens for RBP, we revisited and improved existing RNA-Y3H methodology by (1) implementing full-length ORF libraries in combination with (2) efficient yeast mating to increase screening depth and sensitivity, and (3) stringent negative controls to eliminate over-representation of non-specific RNA-binders. These improvements were validated employing the well-characterized interaction between DDX6 (DEAD-box helicase 6) and sfRNA of DENV as paradigm. Our advanced Y3H system was used to screen for human proteins binding to DENV and ZIKV sfRNA, resulting in a list of 69 putative sfRNA-binders, including several previously reported as well as numerous novel RBP host factors. Our methodology requiring no sophisticated infrastructure or analytic pipeline may be employed for the discovery of meaningful RNA–protein interactions at large scale in other fields.