The purpose of this study is to research the antecedents of the sustainable travel decision-making of European travelers and thereby identify important lessons for the transition towards sustainable travel and tourism. The study is based on data collected through a representative survey, conducted in five European countries, with a sample of n = 5024 respondents. The results of descriptive statistics, EFA (Exploratory Factor Analysis) and FA (Factor Analysis) are presented in order to explore sustainable travel decision-making through environmental (policy-related and personal) attitudes and travel mode decision priorities in the European context. Furthermore, the study provides new evidence regarding the under-researched phenomenon of the attitude–behavior gap by presenting a model for the sustainability-oriented decision-making of travelers, including attitudes and travel mode priorities as antecedents. The results confirm the existence of moral licensing in travel decision-making, thereby extending the relevance of this theory into travel and tourism, which has not been done before. The denial of environmental issues is also being researched as regards its interaction with positive environmental attitudes, environmental travel mode priorities and non-environmental travel priorities, thereby advancing our understanding of the interplay between these categories. The interplay between the four categories furthers our understanding of the perplexity of travelers in terms of sustainable travel decision-making.