Migration and invasion are key properties of metastatic cancer cells. These properties can be acquired through intrinsic reprogramming processes such as epithelial-mesenchymal transition. In this study, we discovered an alternative “migration-by-tethering” mechanism through which cancer cells gain the momentum to migrate by adhering to mesenchymal stem cells or osteoblasts. This tethering is mediated by both heterotypic adherens junctions and gap junctions, and leads to a unique cellular protrusion supported by cofilin-coated actin filaments. Inhibition of gap junctions or depletion of cofilin reduces migration-by-tethering. We observed evidence of these protrusions in bone segments harboring experimental and spontaneous bone metastasis in animal models. These data exemplify how cancer cells may acquire migratory ability without intrinsic reprogramming. Furthermore, given the important roles of osteogenic cells in early-stage bone colonization, our observations raise the possibility that migration-by-tethering may drive the relocation of disseminated tumor cells between different niches in the bone microenvironment.