Ca²⁺ regulates voltage-gated Na⁺ (Na_V) channels, and perturbed Ca²⁺ regulation of Na_V function is associated with epilepsy syndromes, autism and cardiac arrhythmias. Understanding the disease mechanisms, however, has been hindered by a lack of structural information and competing models for how Ca²⁺ affects Na_V channel function. Here we report the crystal structures of two ternary complexes of a human Na_V cytosolic C-terminal domain (CTD), a fibroblast growth factor homologous factor and Ca²⁺/calmodulin (Ca²⁺/CaM). These structures rule out direct binding of Ca²⁺ to the Na_V CTD and uncover new contacts between CaM and the Na_V CTD. Probing these new contacts with biochemical and functional experiments allows us to propose a mechanism by which Ca²⁺ could regulate Na_V channels. Further, our model provides hints towards understanding the molecular basis of the neurologic disorders and cardiac arrhythmias caused by Na_V channel mutations.