Postoperative delirium (POD) is associated with increased complication and mortality rates, particularly among older adult patients. However, guideline recommendations for POD detection and management are poorly implemented. Fast-and-frugal trees (FFTrees), which are simple prediction algorithms, may be useful in this context. We compared the capacity of simple FFTrees with two more complex models—namely, unconstrained classification trees (UDTs) and logistic regression (LogReg)—for the prediction of POD among older surgical patients in the perioperative setting. Models were trained and tested on the European BioCog project clinical dataset. Based on the entire dataset, two different FFTrees were developed for the pre-operative and postoperative settings. Within the pre-operative setting, FFTrees outperformed the more complex UDT algorithm with respect to predictive balanced accuracy, nearing the prediction level of the logistic regression. Within the postoperative setting, FFTrees outperformed both complex models. Applying the best-performing algorithms to the full datasets, we proposed an FFTree using four cues (Charlson Comorbidity Index (CCI), site of surgery, physical status and frailty status) for the pre-operative setting and an FFTree containing only three cues (duration of anesthesia, age and CCI) for the postoperative setting. Given that both FFTrees contained considerably fewer criteria, which can be easily memorized and applied by health professionals in daily routine, FFTrees could help identify patients requiring intensified POD screening.