Significance RNA regulation occurs at many levels including processing to mature forms, subcellular localization, and translation. RNA-binding proteins are crucial to direct and regulate these processes. Pumilio/feminization of XX and XO animals (fem)-3 mRNA-binding factor (PUF) proteins are RNA-binding proteins formed from eight α-helical repeats [Pumilio (PUM) repeats] that recognize specific mRNA sequences. Previous structural studies revealed characteristic curved structures and sequence specificity unique to these classical PUF proteins. We show here that PUM repeats also form different folds with 11 PUM repeats. Moreover, these proteins, exemplified by human Puf-A and yeast Puf6 proteins, recognize double-stranded RNA or DNA without sequence specificity. Interestingly, Puf-A and Puf6 PUM repeats lack specificity for RNA bases yet use residues at conserved positions on topologically equivalent protein surfaces for new nucleic acid recognition modes.