A better understanding of the features that define the interaction between cancer cells and immune cells is important for the development of new cancer therapies1. However, focus is often given to interactions that occur within the primary tumour and its microenvironment, whereas the role of immune cells during cancer dissemination in patients remains largely uncharacterized2,3. Circulating tumour cells (CTCs) are precursors of metastasis in several types of cancer4-6, and are occasionally found within the bloodstream in association with non-malignant cells such as white blood cells (WBCs)7,8. The identity and function of these CTC-associated WBCs, as well as the molecular features that define the interaction between WBCs and CTCs, are unknown. Here we isolate and characterize individual CTC-associated WBCs, as well as corresponding cancer cells within each CTC-WBC cluster, from patients with breast cancer and from mouse models. We use single-cell RNA sequencing to show that in the majority of these cases, CTCs were associated with neutrophils. When comparing the transcriptome profiles of CTCs associated with neutrophils against those of CTCs alone, we detect a number of differentially expressed genes that outline cell cycle progression, leading to more efficient metastasis formation. Further, we identify cell-cell junction and cytokine-receptor pairs that define CTC-neutrophil clusters, representing key vulnerabilities of the metastatic process. Thus, the association between neutrophils and CTCs drives cell cycle progression within the bloodstream and expands the metastatic potential of CTCs, providing a rationale for targeting this interaction in treatment of breast cancer.