Purpose To derive a decision rule for predicting surgical complexity in periorbital basal cell carcinoma (pBCC). Design Prospective, cohort study. Participants Patients referred to an oculoplastic service for excision of pBCC from September 2010 to November 2015 Methods This study was conducted at two centres in New Zealand from September 2010 to November 2015. Baseline demographic information, and an initial assessment of operative complexity (a four-point grading scale) were collected. Assessment of operative complexity was repeated at the time of reconstruction. Univariate analysis was applied to identify the associative factors and supervised machine learning was used to determine the best predictive models to construct a clinical decision rule. Main outcome measures Pre- and post-operative surgical complexity. Results 156 patients and 156 periocular BCC were analysed. Univariate analysis revealed that older age, recurrent skin cancer, large, tumour size, being a public patient, and high complexity at preoperative assessment were associated with high actual operative complexity. Tumour histology was not associated with more complex surgery. Machine learning analyses revealed that Naive Bayesian classifier was able to distinguish surgical complexity with an average area under the receiver operating characteristic curve (AUC) of 0.854 (95% C.I. 0.762-0.946) whereas a simpler, alternating decision tree (ADT) that used only three clinical variables achieved an AUC of 0.853 (95% C.I. 0.739-0.931). The ADT model was 10.1 times more likely to correctly identify a high complexity case. The three predictive variables were pre-operative assessment of complexity (high versus low), surgical delays [early (