In mammals, A+U-rich elements (AREs) are potent cis-acting determinants of rapid cytoplasmic mRNA turnover. Recognition of these sequences by AUF1 is associated with acceleration of mRNA decay, likely involving recruitment or assembly of multi-subunit transacting complexes. Previously, we demonstrated that AUF1 deletion mutants formed tetramers on U-rich RNA substrates by sequential addition of protein dimers (Wilson, G. M., Sun, Y., Lu, H,, and Brewer, G, (1999) J, Biol. Chem. 274, 33374-33381). Here, we show that binding of the full-length p37 isoform of AUF1 to these RNAs proceeds via a similar mechanism, allowing delineation of equilibrium binding constants for both stages of tetramer assembly. However, association of AUF1 with the ARE from tumor necrosis factor (TNF alpha) mRNA was significantly inhibited by magnesium ions. Further fluorescence and hydrodynamic experiments indicated that Mg2+ induced or stabilized a conformational change in the TNF alpha ARE. Based on the solution of parameters describing both the protein-RNA and Mg2+-RNA equilibria, we present a dynamic, global equilibrium binding model describing the relationship between Mg2+ and AUF1 binding to the TNF alpha ARE. These studies provide the first evidence that some AREs may adopt higher order RNA structures that regulate their interaction with traits-acting factors and indicate that mRNA structural remodeling has the potential to modulate the turnover rates of some ARE-containing mRNAs.