Air traffic complexity, an essential attribute of air traffic situation, is the main driving force of workload for air-traffic controllers and is the key to achieving refined air traffic control. The existing air traffic complexity studies are based on static network, ignoring the dynamic evolution of between-aircraft proximity relations. Research on such evolution course and propagation characteristics will help to comprehensively explore the mechanisms of complexity formation. Herein, an air traffic complexity propagation research method based on temporal networking and disease propagation modeling is proposed. First, a temporal network is built with aircraft as nodes and between-aircraft proximity relations as edges. Second, the disease propagation model is introduced to simulate the evolution course of between-aircraft proximity relations, and the propagation model is solved using Runge–Kutta algorithm and particle swarm optimization. Third, based on the solved results of the propagation model, the aircraft are divided into three groups with high, medium, and low propagation capability, respectively. Finally, the effects of different factors on the propagation course are analyzed using multivariate linear regression. Real data validation shows the propagation of high-propagation capability aircraft is significantly affected by duration, and the temporal-correlation coefficient. The propagation of medium-propagation capability aircraft is significantly affected by duration and the clustering degree. By adjusting the influencing factors, the air traffic complexity propagation process can be effectively controlled.