Calcium/calmodulin-dependent kinase II (CaMKII) plays a key role in the plasticity of dendritic spines. Calcium signals cause calcium-calmodulin to activate CaMKII, which leads to remodeling of the actin filament (F-actin) network in the spine. We elucidate the mechanism of the remodeling by combining computer simulations with protein array experiments and electron microscopic imaging, to arrive at a structural model for the dodecameric complex of CaMKII with F-actin. The binding interface involves multiple domains of CaMKII. This structure explains the architecture of the micrometer-scale CaMKII/F-actin bundles arising from the multivalence of CaMKII. We also show that the regulatory domain of CaMKII may bind either calmodulin or F-actin, but not both. This frustration, along with the multipartite nature of the binding interface, allows calmodulin transiently to strip CaMKII from actin assemblies so that they can reorganize. This observation therefore provides a simple mechanism by which the structural dynamics of CaMKII establishes the link between calcium signaling and the morphological plasticity of dendritic spines.