Tumor metastasis is driven not only by the accumulation of intrinsic alterations in malignant cells, but also by the interactions of cancer cells with various stromal cell components of the tumor microenvironment. In particular, inflammation and infiltration of the tumor tissue by host immune cells, such as tumor-associated macrophages, myeloid-derived suppressor cells, and regulatory T cells, have been shown to support tumor growth in addition to invasion and metastasis. Each step of tumor development, from initiation through metastatic spread, is promoted by communication between tumor and immune cells via the secretion of cytokines, growth factors, and proteases that remodel the tumor microenvironment. Invasion and metastasis require neovascularization, breakdown of the basement membrane, and remodeling of the extracellular matrix for tumor cell invasion and extravasation into the blood and lymphatic vessels. The subsequent dissemination of tumor cells to distant organ sites necessitates a treacherous journey through the vasculature, which is fostered by close association with platelets and macrophages. Additionally, the establishment of the pre-metastatic niche and specific metastasis organ tropism is fostered by neutrophils and bone marrow-derived hematopoietic immune progenitor cells and other inflammatory cytokines derived from tumor and immune cells, which alter the local environment of the tissue to promote adhesion of circulating tumor cells. This review focuses on the interactions between tumor cells and immune cells recruited to the tumor microenvironment and examines the factors allowing these cells to promote each stage of metastasis.