Efficient commercial airline operations rely extensively on consistent and timely flight departure and arrival times, adherence to regular maintenance schedules, and minimizing unexpected service interruptions. Such interruptions include mechanical malfunctions that require unscheduled removal and replacement of a part or component. This necessarily causes cascading delays, consequential customer dissatisfaction, and increased costs. In this paper, we propose a novel clustering-based framework that takes historical (scheduled and unscheduled) maintenance events for aircraft, to predict when the next maintenance event will occur. We identify clusters of aircraft sharing similar spatio-temporal performance patterns, and define a prediction model over each cluster. We show that our models achieve improved accuracy over naive and baseline approaches, under varying parameters, airline carriers, and aircraft part components.