Unplanned hospital readmissions are a key indicator of quality in healthcare and can lead to high unnecessary costs for the hospital due to additional required resources or reduced payments by insurers or governments. Predictive analytics can support the identification of patients at high-risk for readmission early on to enable timely interventions. In Australia, hysterectomies present the 2nd highest observed readmission rates of all surgical procedures in public hospitals. Prior research so far only focuses on developing explanatory models to identify associated risk factors for past patients. In this study, we develop and compare 24 prediction models using state-of-the-art sampling and ensemble methods to counter common problems in readmission prediction, such as imbalanced data and poor performance of individual classifiers. The application and evaluation of these models are presented, resulting in an excellent predictive power with under- and oversampling and an additional slight increase in performance when combined with ensemble methods.