Performance analysis of the air traffic operations is challenging because of the need to account for weather impacts and network effects. In this paper, we propose a framework that uses network clustering to identify baselines for benchmarking airline on-time performance. We demonstrate our framework by computing cancellation and departure delay baselines using US flight data for the years 2014–16. Subsequently, we use these baselines to benchmark daily on-time performance at the system-wide, airline-, and airport-specific levels, for both mainline and regional carriers. This framework enables an airline to conduct self- and peer-comparisons, evaluate improvements over time, and diagnose causes of poor on-time performance. Furthermore, our framework can be used by system operators to identify long-term trends in traffic management initiatives.