Understanding people’s travel behavior is key to creating spaces that discourage car use, especially for short, walkable distances. The scope of this study is to understand better people’s propensity to use a car rather than walk for short-distance trips by focusing on the concept of perceived exertion (PE). A comparison is performed of two case study locations: Malta, a Euro-Mediterranean island with a high car dependency, and the Netherlands, a European country with a high active mode share of walking and cycling. Surveys were distributed to two university populations in each of the case study locations to analyze the parallels and variations in travel behavior and perceptions. Applying a mediation model analysis, the results show a partial mediation (Malta) and a full mediation (Netherlands) of PE in the relationship between car use frequency (CF) and distance threshold (DT), that is, the distance people are willing to walk rather than use a car. The mean DT for walking varied significantly between the two samples, resulting in 15.18 min (1.2 km or 0.7 mi) in the Netherlands and 17.99 min (1.4 km or 0.9 mi) in Malta, despite the comparatively larger active mode share in the Netherlands. Complementing this, the ordinal logistic models for the two countries indicate that those that perceive walking for short trips to be more effortful and those with a high CF are less inclined to walk long distances. Findings are compared with previous research, and policy-relevant suggestions based on these findings are provided.