Fast amoeboid migration is critical for developmental processes and can be hijacked by cancer cells to enhance metastatic dissemination. This migratory behavior is tightly controlled by high levels of actomyosin contractility, but how it is coupled to other cytoskeletal components is poorly understood. Septins are increasingly recognized as novel cytoskeletal components, but details on their regulation and contribution to migration are lacking. Here, we show that the septin regulator Cdc42EP5 is consistently required for amoeboid melanoma cells to invade and migrate into collagen-rich matrices and locally invade and disseminate in vivo. Cdc42EP5 associates with actin structures, leading to increased actomyosin contractility and amoeboid migration. Cdc42EP5 affects these functions through SEPT9-dependent F-actin cross-linking, which enables the generation of F-actin bundles required for the sustained stabilization of highly contractile actomyosin structures. This study provides evidence that Cdc42EP5 is a regulator of cancer cell motility that coordinates actin and septin networks and describes a unique role for SEPT9 in melanoma invasion and metastasis.