Independent studies indicate that expression of sialylated fucosylated mucins by human carcinomas portends a poor prognosis because of enhanced metastatic spread of tumor cells, that carcinoma metastasis in mice is facilitated by formation of tumor cell complexes with blood platelets, and that metastasis can be attenuated by a background of P-selectin deficiency or by treatment with heparin. The effects of heparin are not primarily due to its anticoagulant action. Other explanations have been suggested but not proven. Here, we bring together all these unexplained and seemingly disparate observations, showing that heparin treatment attenuates tumor metastasis in mice by inhibiting P-selectin-mediated interactions of platelets with carcinoma cell-surface mucin ligands. Selective removal of tumor mucin P-selectin ligands, a single heparin dose, or a background of P-selectin deficiency each reduces tumor cell-platelet interactions in vitro and in vivo. Although each of these maneuvers reduced the in vivo interactions for only a few hours, all markedly reduce long-term organ colonization by tumor cells. Three-dimensional reconstructions by using volume-rendering software show that each situation interferes with formation of the platelet “cloak” around tumor cells while permitting an increased interaction of monocytes (macrophage precursors) with the malignant cells. Finally, we show that human P-selectin is even more sensitive to heparin than mouse P-selectin, giving significant inhibition at concentrations that are in the clinically acceptable range. We suggest that heparin therapy for metastasis prevention in humans be revisited, with these mechanistic paradigms in mind.