This study analyses the interrelationship between economic policy uncertainty (EPU) and tourism in Mediterranean Basin countries for the period 1997–2020. The paper includes two analyses along with two models. The first analysis investigates a long-run relationship between variables and estimates long-run coefficients by using the Method of Moment Quantile Regression (MM-QR) technique, a novel approach that provides more comprehensive insights. The second analysis examines the dynamic relationship between the variables by dynamic Kónya panel symmetric and asymmetric causality tests. According to the MM-QR estimation results, the effect of EPU on international tourist arrivals (ITA) in Model I is positive across all quantiles (except at the 0.1 quantile), and this positive effect increases with quantile level. In Model II, the effect of ITA on EPU is positive for most of the quantiles (except at the 0.8 and 0.9 quantiles). However, it is statistically significant only for countries in the 0.2 quantile group. The dynamic symmetric causality findings indicate a causal relationship from tourism to EPU (except for Spain) and from EPU to tourism for all countries. The dynamic asymmetric causality test reveals an asymmetric causality in the positive component from tourism to EPU in various periods across countries (except for Greece). In the positive component from EPU to tourism, we observed causality relationships in France and Spain (in a single period) and in Greece and Italy (across multiple periods). It is first study in the literature to examine the causal relationship between EPU and tourism by using dynamic symmetric and asymmetric bootstrap panel causality tests, with a focus on Mediterranean Basin countries. It therefore addresses a significant gap in literature. It is found that there is strong sensitivity in the relationship between tourism and EPU, hence policymakers must carefully calibrate their strategies when assessing the interaction between these two critical factors.