Introduction: Basal cell carcinoma (BCC) is the most frequent malignant skin tumor. BCC rarely metastasizes, but it is often locally aggressive. Cyclooxygenase-2 (COX-2) is critical for tumor formation, angiogenesis and metastasis. Matrix metalloproteinases (MMPs) are the members of the family of zinc (Zn)- and calcium-dependent endopeptidases that degrade the extracellular matrix. Materials and Methods: In our study, we used immunohistochemical methods for the evaluation of COX-2, MMP-2 and MMP-9 expression in tissue samples of 30 primary and 10 recurrent skin BCC cases. Results: Immunohistochemical COX-2 expression was significantly higher in the infiltrating pattern of BCC compared with the nodular (P = 0.005) and superficial (P = 0.041) subtypes in the primary BCC group. There was not a significant difference between nodular and superficial BCCs for COX-2 expression. In addition, COX-2 expression was significantly higher in the recurrent BCC group than in the primary BCC group (P = 0.030). There was no statistically significant difference between the histological subtypes of primary BCCs and between primary and recurrent BCCs for MMP-2 and MMP-9 expressions. Conclusions: Our data confirm previous findings that COX-2 and MMP-9 expressions are increased in BCC. Our results revealed an elevated COX-2 expression in recurrent BCCs. We suggest that COX-2 inhibition might have beneficial effects in BCCs, especially for the tumors with a higher level of COX-2 expression or aggressive phenotype.