The ability of cancer cells to metastasize is dependent on the interactions between their cell-surface molecules and the microenvironment. However, the tumor microenvironment, especially the cancer-associated stroma, is poorly understood. To identify proteins present in the stroma, we focused on phyllodes tumors, rare breast tumors that contain breast stromal cells. We compared the expression of proteins between phyllodes tumor and normal tissues using an iTRAQ-based quantitative proteomic approach. Decorin was expressed at reduced levels in phyllodes tumor tissues, whereas periostin was upregulated; this result was validated by immunohistochemical analysis of phyllodes tumors from 35 patients. Additionally, by immunoprecipitation and mass spectrometry, we confirmed that decorin forms a complex with periostin in both phyllodes tumors and BT-20 breast cancer cells. Following siRNA-mediated knockdown of periostin in T-47D cells, secreted decorin in the culture medium could be detected by multiple reaction monitoring (MRM). Furthermore, periostin knockdown in BT-20 cells and overexpression of decorin in MDA-MB-231 cells inhibited cell motility and invasion. Our results reveal the molecular details of the periostin-decorin complex in both phyllodes tumor tissues and breast cancer cells; this interaction may represent a novel target for anti-cancer therapy.