The commencement of regular nonstop flights between mainland China and Taiwan in December 2008 was expected to increase the flow of traffic across the Taiwan Strait. Travelers would no longer have to stop to change aircraft; the flight between mainland China and Taiwan would be quicker, cheaper, and more convenient. Hong Kong and Macau, formerly the gateways connecting Taiwan to China, would now compete with point-to-point nonstop flights available to cross-strait travelers. The aim of this study was to examine the evolving supply and demand associated with the aviation market between China and Taiwan and to focus on the changes resulting from the introduction of scheduled nonstop flights. Data covering a 15-month period were collected and analyzed by using multilevel models. The results show that despite rapid growth in the nonstop cross-strait air travel market, growth rates are still restricted by limitations set by the Chinese and Taiwanese governments, particularly those routes connecting Taiwan with first-tier Chinese cities. For this reason, some travelers are forced to make a detour through Hong Kong or Macau on their way to China. However, city pairs connecting Taiwan with second- or third-tier Chinese cities have not performed as well as expected, and some markets have even demonstrated a negative trend over time, indicating a shrinking market. The market for cross-strait air travel exhibits clear heterogeneous characteristics in city pairs, which should be considered as governments take the next steps in opening up the market.