M2 macrophages promote tumor growth and metastasis, but their interactions with specific tumor cell populations are poorly characterized. Using a mouse model of spontaneous melanoma, we showed that CD34- but not CD34+ tumor-initiating cells (TICs) depend on M2 macrophages for survival and proliferation. Tumor-associated macrophages (TAMs) and macrophage-conditioned media protected CD34- TICs from chemotherapy in vitro. In vivo, while inhibition of CD115 suppressed the macrophage-dependent CD34- TIC population, chemotherapy accelerated its development. The ability of TICs to respond to TAMs was acquired during melanoma progression and immediately preceded a surge in metastatic outgrowth. TAM-derived transforming growth factor-β (TGFβ) and polyamines produced via the Arginase pathway were critical for stimulation of TICs and synergized to promote their growth.