Nevoid basal cell carcinoma syndrome (NBCCS) associated odontogenic keratocysts (OKCs) show more aggressive behavior and it has a higher frequency of relapse than non-syndromic OKCs. Stromal myofibroblasts (MFs), characterized by α-smooth muscle actin (αSMA), desmin and caldesmon expression, and metalloproteinases (MMPs) have an essential role in the remodeling of the extracellular matrix (ECM). The aim of the study is to analyze the immunohistochemical expression of MMP-7, MMP-9, αSMA and other new markers in the study of OKCs MFs such as desmin and caldesmon in NBCCS-associated OKCs compared to recurrent and sporadic keratocysts. Fourty 40 patients (23 M and 17 F) underwent surgery to remove the OKCs. The histological sections in paraffin were incubated with markers antibodies and a semi-quantitative score was used to evaluate the immunoreactivity. Densitometric analysis showed a very significantly increased expression of αSMA, caldesmon, MMP-7 and MMP-9 in NBCCS-OKCs compared to non-syndromic OKCs (p < 0.001). However, desmin showed a not significant increased expression in non-syndromic OKC compared to NBCCS-OKCs specimens in which desmin was slightly or not at all expressed. NBCSS-OKCs showed a greater distribution of MFs compared to the other OKCs subtypes. Further studies will be needed to evaluate whether the different expressions of these markers can be correlated to a different clinical behavior.