Processing bodies (P-bodies) are cytoplasmic RNA granules that contain translationally repressed messenger ribonucleoproteins (mRNPs) and messenger RNA (mRNA) decay factors. The physical interactions that form the individual mRNPs within P-bodies and how those mRNPs assemble into larger P-bodies are unresolved. We identify direct protein interactions that could contribute to the formation of an mRNP complex that consists of core P-body components. Additionally, we demonstrate that the formation of P-bodies that are visible by light microscopy occurs either through Edc3p, which acts as a scaffold and cross-bridging protein, or via the "prionlike" domain in Lsm4p. Analysis of cells defective in P-body formation indicates that the concentration of translationally repressed mRNPs and decay factors into microscopically visible P-bodies is not necessary for basal control of translation repression and mRNA decay. These results suggest a stepwise model for P-body assembly with the initial formation of a core mRNA-protein complex that then aggregates through multiple specific mechanisms.