Basal cell carcinoma (BCC) is the most common skin malignancy worldwide. Current evidence suggests tumour-infiltrating lymphocytes (TILs) may influence the clinical outcomes of patients with BCC. The present study aimed to profile the infiltrative characteristics of stromal TILs and regulatory T cells (Treg cells) in the tumour centre (TC), tumour periphery (TP), and normal adjacent tissue (NAT) of BCC. A total of 111 samples from 43 cutaneous BCC cases were examined for TIL (CD3+) and Treg cell (FOXP3+/CD3+) expression using immunohistochemical techniques. The correlations of Treg cells with TILs, invasion depth, and tumour morphological risk were analysed. We identified a high mean proportion of Treg cells within the tumour (TC = 46.9%, TP = 56.1%, NAT = 51.8%) despite a relatively low median of TILs (TC = 12.7%, TP = 10.3%, NAT = 3.6%), supporting the classification of BCC as a cold tumour. A significant positive correlation was observed between the proportion of Treg cells and sTILs (ρ = 0.325, p < 0.001), suggesting a predominant role of TILs in the infiltration of Treg cells. An inverse correlation discovered between Treg cells and tumour invasion depth (r = −0.36, p = 0.017) might indicate Treg cells’ anti-tumour capacity in BCC.