Background: Cutaneous basal cell carcinoma (BCC) is the commonest cancer worldwide. BCC is locally invasive and the surrounding stromal microenvironment is pivotal for tumourigenesis. Cancer associated fibroblasts (CAFs) in the microenvironment are essential for tumour growth in a variety of neoplasms but their role in BCC is poorly understood. Methods: Material included facial BCC and control skin from the peritumoural area and from the buttocks. With next-generation sequencing (NGS) we compared mRNA expression between BCC and peritumoural skin. qRT-PCR, immunohistochemical and immunofluorescent staining were performed to validate the NGS results and to investigate CAF-related cyto-and chemokines. Results: NGS revealed upregulation of 65 genes in BCC coding for extracellular matrix components pointing at CAF-related matrix remodeling. qRT-PCR showed increased mRNA expression of CAF markers FAP-α, PDGFR-β and prolyl-4-hydroxylase in BCC. Peritumoural skin (but not buttock skin) also exhibited high expression of PDGFR-β and prolyl-4-hydroxylase but not FAP-α. We found a similar pattern for the CAF-associated chemokines CCL17, CCL18, CCL22, CCL25, CXCL12 and IL6 with high expression in BCC and peritumoural skin but absence in buttock skin. Immunofluorescence revealed correlation between FAP-α and PDGFR-β and CXCL12 and CCL17. Conclusion: Matrix remodeling is the most prominent molecular feature of BCC. CAFs are present within BCC stroma and associated with increased expression of chemokines involved in tumour progression and immunosuppression (CXCL12, CCL17). Fibroblasts from chronically sun-exposed skin near tumours show gene expression patterns resembling that of CAFs, indicating that stromal fibroblasts in cancer-free surgical BCC margins exhibit a tumour promoting phenotype.