The structural basis for binding of the acidic transcription activator Gcn4 and one activator-binding domain of the Mediator subunit Gal11/Med15 was examined by NMR. Gal11 activator-binding domain 1 has a four-helix fold with a small shallow hydrophobic cleft at its center. In the bound complex, eight residues of Gcn4 adopt a helical conformation, allowing three Gcn4 aromatic/aliphatic residues to insert into the Gal11 cleft. The protein-protein interface is dynamic and surprisingly simple, involving only hydrophobic interactions. This allows Gcn4 to bind Gal11 in multiple conformations and orientations, an example of a "fuzzy" complex, where the Gcn4-Gal11 interface cannot be described by a single conformation. Gcn4 uses a similar mechanism to bind two other unrelated activator-binding domains. Functional studies in yeast show the importance of residues at the protein interface, define the minimal requirements for a functional activator, and suggest a mechanism by which activators bind to multiple unrelated targets.