Passenger flows among cities, at both the domestic and international levels and in different countries and regions, have been studied for forecasting purposes. This paper seeks not a forecasting mechanism, but to understand, by analyzing passenger origins and destinations by Brazilian sub-region, how Brazil’s domestic air passenger network links have evolved. Using income, population, and fare price as inputs, and seats sold as output, air link performance is examined by data envelopment analysis to discuss the regional link of domestic passenger traffic in Brazil and its dynamics, considering two specific years. The findings indicate that, although the highest passenger flow density is concentrated in Brazil’s Southeast region, performance by emerging origins and destinations (O-Ds), such as those connecting the Northeast, display more substantial strength indices and advances (Malmquist analysis). The analysis of specific links was also important, which showed that important Brazilian airports are not necessarily more competent in generating trips. The Catch-Up indicator for innovation reveals the weak point in Brazil’s air transport network. Although some airports enjoy strong networkability, they do not correspond in passenger origin or destination strength.