Background Tumor cell subpopulations can either compete with each other for nutrients and physical space within the tumor niche, or co-operate for enhanced survival, or replicative or metastatic capacities. Recently, we have described co-operative interactions between two clonal subpopulations derived from the PC-3 prostate cancer cell line, in which the invasiveness of a cancer stem cell (CSC)-enriched subpopulation (PC-3M, or M) is enhanced by a non-CSC subpopulation (PC-3S, or S), resulting in their accelerated metastatic dissemination. Methods M and S secretomes were compared by SILAC (Stable Isotope Labeling by Aminoacids in Cell Culture). Invasive potential in vitro of M cells was analyzed by Transwell-Matrigel assays. M cells were co-injected with S cells in the dorsal prostate of immunodeficient mice and monitored by bioluminescence for tumor growth and metastatic dissemination. SPARC levels were determined by immunohistochemistry and real-time RT-PCR in tumors and by ELISA in plasma from patients with metastatic or non-metastatic prostate cancer. Results Comparative secretome analysis yielded 213 proteins differentially secreted between M and S cells. Of these, the protein most abundantly secreted in S relative to M cells was SPARC. Immunodepletion of SPARC inhibited the enhanced invasiveness of M induced by S conditioned medium. Knock down of SPARC in S cells abrogated the capacity of its conditioned medium to enhance the in vitro invasiveness of M cells and compromised their potential to boost the metastatic behavior of M cells in vivo. In most primary human prostate cancer samples, SPARC was expressed in the epithelial tumoral compartment of metastatic cases. Conclusions The matricellular protein SPARC, secreted by a prostate cancer clonal tumor cell subpopulation displaying non-CSC properties, is a critical mediator of paracrine effects exerted on a distinct tumor cell subpopulation enriched in CSC. This paracrine interaction results in an enhanced metastatic behavior of the CSC-enriched tumor subpopulation. SPARC is expressed in the neoplastic cells of primary prostate cancer samples from metastatic cases, and could thus constitute a tumor progression biomarker and a therapeutic target in advanced prostate cancer.