Anterior-posterior axis patterning of the Drosophila embryo requires Nanos activity selectively in the posterior. This spatial asymmetry of Nanos is generated by the localization of nanos mRNA to the posterior pole of the embryo, where it is subsequently translated. Posterior localization of nanos is mediated by a complex cis-acting localization signal in its 3' untranslated region comprising several partially redundant localization elements. This localization signal redundancy has hampered the identification of trans-acting factors that act specifically to effect posterior localization of nanos. Here, we have used a biochemical approach to identify Rumpelstiltskin, a Drosophila heterogeneous nuclear ribonucleoprotein (hnRNP) M homolog, which binds directly to an individual nanos localization element. Rumpelstiltskin associates with nanos mRNA in vitro and in vivo, and binding by Rumpelstiltskin correlates with localization element function in vivo. Through analysis of a rumpelstiltskin null mutation by genetic strategies that circumvent redundancy, we demonstrate that Rumpelstiltskin regulates anterior-posterior axis patterning by functioning as a direct-acting nanos mRNA localization factor.