Air Traffic Controllers’ (ATCos) mental workload is likely to remain the specific greatest functional limitation on the capacity of the Air Traffic Management (ATM) system. Developing computational models to monitor mental workload and task complexity is essential for enabling ATCOs and ATM systems to adapt to varying task demands. Most methodologies have computed task complexity based on basic parameters such as air-traffic density; however, literature research has shown that it also depends on many other factors. In this paper, we present a study in which we explored the possibility of predicting task complexity and performance through mental workload measurements of participants performing an ATM task in an air-traffic control simulator. Our findings suggest that mental workload measurements better predict poor performance and high task complexity peaks than other established factors. This underscores their potential for research into how different ATM factors affect task complexity. Understanding the role and the weight of these factors in the overall task complexity confronted by ATCos constitutes one of the biggest challenges currently faced by the ATM sphere and would significantly contribute to the safety of our sky.