The growing demand for air travel has led to the saturation of air traffic networks. Conventional methods of adding routes to alleviate congestion and reduce delays may not achieve the desired effect and even degrade system performance. In this paper, we explore the application of Braess’s Paradox in the reduction of air traffic networks. This counterintuitive phenomenon shows that adding new connections to a network can actually increase the overall network pressure. This study uses Hidden Markov methods and the Viterbi algorithm to match air traffic flow with routes, a machine learning approach and a mathematical method to construct cost functions for flight time and traffic volume, and finally uses genetic algorithm and the A* algorithm to detect Braess’s Paradox edges. We uses ADS-B data from the busy month of July 2019 for a case study of the air traffic network over the UK airspace. The results show that Braess’s Paradox is also applicable to multi-flight level air route networks. Removing such network edges can improve system performance. In one day’s case, the total flight time of the day’s traffic volume decreased from 11509.24 minutes to 10459.97 minutes. This equates to an average savings of 4.99 minutes of flight time per flight, which is significant in controlling delay performance.