Travel itineraries between many origin‐destination (OD) pairs can require multiple legs, such as several trains, shared rides or flights, to arrive at the final destination. Travelers expect transparent reliability information to help improve decision‐making for multi‐leg itineraries. We focus on airline travel and making a priori decisions about flight itineraries based on the reliability of arriving at the destination within the travel time budget. We model the reliability of multi‐leg itineraries and, given publicly available data, create probability distributions of flight arrival and departure times. We use these values in our reliability calculations for the entire itinerary. We implement a stochastic network search algorithm that finds the most reliable flight itinerary (MRFI). We also implement several ideas to improve the efficiency of this network search. Computational experiments help identify characteristics of the MRFI for a diverse set of OD pairs.