Background: Basal cell carcinoma (BCC) incidence is steadily increasing but therapeutic solutions remain limited and present a public health challenge. Aims: To identify predictive factors of BCC recurrence after primary free margin excision, with automated methods, by evaluating cell proliferation, the Hedgehog pathway activation and primary cilia. Materials and Methods: This case–control study included 32 patients (16 with recurrence occurring at least 6 months after complete resection, and 16 without recurrence) who underwent surgery for BCC. Formalin-fixed paraffin-embedded cutaneous resections were processed for immunohistochemistry or immunostaining with the following primary antibodies: mouse anti-MCM6, rabbit anti-ARL13B and rabbit anti-GLI1. Results: BCC recurrence after free margin excision was significantly linked to a higher proliferative index (p < 0.001) and a lower cilia count (p = 0.041) in the primary lesion. No significant differences were observed regarding cilia length (p = 0.39) or GLI1-positive nuclei. Discussion: The complex interplay between essential signaling pathways, cell proliferation and cilia requires further experimental investigations in the context of BCC recurrence. Conclusion: A higher proliferative index evaluated with MCM6 antibody could be a useful prognosis marker of BCC risk of recurrence. The lower cilia count in the primary lesion unveiled novel perspectives to understand BCC recurrence molecular mechanisms.