This paper presents a theoretical model (adapted from the structural gravity model by Anderson and van Wincoop, 2003) to capture the effects of terrorism on air passenger traffic between nations affected by terrorism. We then use equations derived from this model, in conjunction with alternative functional forms for trade costs, to estimate the effects of terrorism on bilateral air passenger flows from 57 source countries to 25 destination countries for the period of 2000 to 2014. We find that an additional terrorist incident results in approximately a 1.2% decrease in the bilateral air passenger transport per unit distance while doubling of the accumulated terrorist incidents during the past 5 years reduces it by 18%. Terrorism adversely impacts the bilateral air passenger transport per unit distance both by reducing national output and especially by increasing psychological distress, which could be an important contributing factor in perceived travel costs. Last but not the least, we show that the responsiveness of international air travel to terrorism critically depends on the nature of the terrorist attacks. Specifically, international air passenger transport is found to be extremely sensitive to fatal terrorist attacks and terrorist attacks of targets such as airports, transportation or tourists.