Exclaves are characterized by several advantages and disadvantages related to physical, economic, historical, social and cultural attributes; these depend on the owner- and the host-state as well as on relationship between the two. Using the case of Ceuta, a Spanish pene-exclave located in north-western Africa bordering Morocco, air travel mobility and accessibility issues faced by residents are identified and discussed primarily in the context of outbound tourism. The empirical research uses a mixed method approach of data collection based on questionnaires distributed to Ceuta residents and participant observation of the local community. Findings suggest that while enhancing accessibility is generally considered to be positive for travel, the reality is more complex in the case of exclaves and pene-exclaves, where geographical discontinuity and lack of land transport connections with the mainland and hinterland of the owner state may co-exist with geo-political conflicts between the owner and the host countries, i.e. Spain and Morocco respectively in the present context. Based on the concept of tourism for peace and its implications for border tourism and the scaling-up of spatial interaction between neighboring regions belonging to different countries, simpler border-crossing procedures along with innovative destination management policies at local level are proposed to improve exclave accessibility and travel mobility in practice to the benefit of both local residents and inbound tourists.