We provide a mathematical formulation of flight-specific delay cost functions that enables a detailed tactical consideration of how a given flight delay will interact with all downstream constraints in the respective aircraft rotation. These functions are reformulated into stochastic delay cost functions to respect conditional probabilities and increasing uncertainty related to more distant operational constraints. Conditional probabilities are learned from historical operations data, such that typical delay propagation patterns can support the flight prioritization process as a part of tactical airline schedule recovery. A case study compares the impact of deterministic and stochastic cost functions on optimal recovery decisions during an airport constraint. We find that deterministic functions systematically overestimate potential disruption costs as well as optimal schedule recovery costs in high delay situations. Thus, an optimisation based on stochastic costs outperforms the deterministic approach by up to 15%, as it reveals ‘hidden’ downstream recovery potentials. This results in different slot allocations and in fewer passengers missing their connections.