Metastasis is a multistep process depending on complex interactions between tumor cells and the stromal compartment which also contains immune cells and soluble factors such as chemokines. The presence of certain classes of monocytes in malignant tumors is frequently a result of chemoattractants such as CCL2 and correlates with enhanced tumor cell extravasation and metastasis. Selectins are vascular adhesion receptors, well-known to facilitate metastasis by mediating the contact between tumor cells and cells in the metastatic environment. Particularly E-selectin is thought to mediate the arrest of tumor cells in the vasculature by binding to E-selectin ligands on tumor cells and thereby promoting metastasis. This study aimed to elucidate whether E-selectin facilitates metastasis by interacting with other constituents of the metastatic microenvironment. Experimental metastasis of tumor cells without E-selectin ligands to the lungs was attenuated in E-selectin deficient mice. This phenotype can already be determined during early metastatic phases. Lung analysis within the first hours after tumor cell injection revealed reduced expression of endothelial activation markers and the chemokine CCL2 in E-selectin deficient mice. Endothelial activation includes E-selectin up-regulation in C57BL/6 mouse lungs and was shown to be partially dependent on tumor cell-derived CCL2. However, endothelial cells and recruited monocytes were identified as the main sources of CCL2 in the metastatic lungs. The total pool of CCL2 in metastatic lungs was decreased in the absence of E-selectin. This is linked to the reduced leukocyte infiltration observed in E-selectin deficient lungs upon tumor cell injection. Association of infiltrated leukocytes with tumor cells was E-selectin dependent. Moreover, monocyte-supported tumor cell transmigration required binding of E-selectin to monocyte ligands. In the presence of E-selectin, tumor cells together with monocytes induced endothelial cell retraction. Accordingly, the lung vasculature was less permeable in E-selectin deficient or monocyte-depleted mice after tumor cell injection. E-selectin deficient mice also showed decreased spontaneous lung metastasis. Our study identifies a novel mechanism how E-selectin-leukocyte interactions supported by CCL2 induce vascular permeability, which promotes tumor cell extravasation and metastasis.