Cancer is a multi-step process, one of the latest events correspond to metastasis formation and dissemination, to date the major cause of deaths. The h-prune-nm23-H1 protein complex and its activation of PDE-cAMP activity have been shown to correlate with breast cancer progression and metastasis formation. Here, we describe the protein complex formation and its involvement in cell migration. By gene expression studies and protein-protein pull-down analyses coupled to mass spectrometry we have identified new genes and pathways along which the h-prune-nm23-H1 complex exerts its function. We review here h-prune binding to the glycogen synthase kinase (GSK-3beta) and identify a new h-prune protein partner, Gelsolin, an ATP severing protein acting in focal adhesions, in a MDA-435 breast cancer cellular model. The results presented here underline the importance of this protein complex leading to new translational studies involved into the inhibition of cell migration, thus enhancing the potential of using this knowledge to direct inhibition of metastases formation in humans.