Air travelers’ satisfaction with current airline options may have different effects on their decisions. We analyzed air passengers’ demands for international round-trip flights using a hybrid discrete choice (HDC) model. Most research on airline choice has only included observable factors, leaving aside issues related to latent variables (LVs). To fill this gap, this study hypothesized that the airline choice process depends not only on a set of measurable factors but also on passenger satisfaction which, in turn, is influenced by travelers’ personality traits. Structural equation modeling was used to construct the satisfaction LV to relate passengers’ personality traits, airline characteristics, and passenger flight experiences with travelers’ perceptions of air carrier services. The satisfaction LV was incorporated into the discrete choice (DC) model, which was used to evaluate travelers’ airline choices for an international round-trip flight on a major Colombia-United States air-route: Medellin (MDE)—Miami (MIA). Results indicated that passenger satisfaction with each airline service was associated with airlines’ utilities. Therefore, by incorporating traveler satisfaction into a DC model, air passenger choice behavior can be modeled more precisely. Hence, a better understanding of travelers’ airline choices can be obtained. Through scenario testing, we also showed how future airline demands might change, depending on how attributes evolve. Further, the average probability of correct predictions in the validation sample reflected the superior fit of the HDC model. These findings highlighted the complex ways in which perceptions can influence airline choice and provided insight for targeted policy interventions.